<!DOCTYPE html>
<html class="client-nojs vector-feature-night-mode-disabled vector-feature-language-in-header-enabled vector-feature-language-in-main-page-header-disabled vector-feature-page-tools-pinned-disabled vector-feature-toc-pinned-clientpref-1 vector-feature-main-menu-pinned-disabled vector-feature-limited-width-clientpref-1 vector-feature-limited-width-content-enabled vector-feature-custom-font-size-clientpref-1 vector-feature-appearance-pinned-clientpref-1 vector-sticky-header-enabled" lang="en" dir="ltr"><head>
<meta charset="UTF-8">
<title>One-way compression function</title>
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<link rel="canonical" href="https://en.wikipedia.org/wiki/One-way_compression_function"> <link href="./mw/ext.cite.styles.css" rel="stylesheet" type="text/css">
<link href="./mw/ext.math.styles.css" rel="stylesheet" type="text/css">
<link href="./mw/skins.vector.icons.css" rel="stylesheet" type="text/css">
<link href="./mw/skins.vector.search.codex.styles.css" rel="stylesheet" type="text/css">
<link href="./mw/skins.vector.styles.css" rel="stylesheet" type="text/css">
<link href="./mw/user.styles.css" rel="stylesheet" type="text/css">
<meta name="ResourceLoaderDynamicStyles" content="">
<link rel="stylesheet" type="text/css" href="./mw/site.styles.css">
<link rel="stylesheet" type="text/css" href="./mw/noscript.css">
<link rel="stylesheet" type="text/css" href="./footer.css">
<link rel="stylesheet" type="text/css" href="./vector-2022.css">
</head>
<body class="skin--responsive skin-vector skin-vector-search-vue mediawiki ltr sitedir-ltr mw-hide-empty-elt ns-0 ns-subject page-One-way_compression_function rootpage-One-way_compression_function skin-vector-2022 action-view">
<div class="mw-page-container">
<div class="mw-page-container-inner">
<div class="mw-content-container">
<main id="content" class="mw-body">
<header class="mw-body-header vector-page-titlebar">
<h1 id="firstHeading" class="firstHeading mw-first-heading">
<span id="openzim-page-title" class="mw-page-title-main"><span class="mw-page-title-main">One-way compression function</span></span>
</h1>
</header>
<a id="top"></a>
<div id="bodyContent" class="vector-body ve-init-mw-desktopArticleTarget-targetContainer" aria-labelledby="firstHeading" data-mw-ve-target-container="">
<div id="mw-content-text" class="mw-body-content mw-content-ltr" lang="en" dir="ltr"><div class="mw-content-ltr mw-parser-output" lang="en" dir="ltr">
<p>In <a href="Cryptography" title="Cryptography">cryptography</a>, a <b>one-way compression function</b> is a function that transforms two fixed-length inputs into a fixed-length output.<sup id="cite_ref-:0_1-0" class="reference"><a href="#cite_note-:0-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup> The transformation is <a href="One-way_function" title="One-way function">"one-way"</a>, meaning that it is difficult given a particular output to compute inputs which compress to that output. One-way compression functions are not related to conventional <a href="Data_compression" title="Data compression">data compression</a> algorithms, which instead can be inverted exactly (lossless compression) or approximately (lossy compression) to the original data.
</p>
<p>One-way compression functions are for instance used in the <a href="Merkle%E2%80%93Damg%C3%A5rd_construction" title="Merkle–Damgård construction">Merkle–Damgård construction</a> inside <a href="Cryptographic_hash_function" title="Cryptographic hash function">cryptographic hash functions</a>.
</p><p>One-way compression functions are often built from <a href="Block_cipher" title="Block cipher">block ciphers</a>.
Some methods to turn any normal block cipher into a one-way compression function are <b>Davies–Meyer</b>, <b>Matyas–Meyer–Oseas</b>, <b>Miyaguchi–Preneel</b> (single-block-length compression functions) and <b>MDC-2/Meyer–Schilling</b>, <b>MDC-4</b>, <b>Hirose</b> (double-block-length compression functions). These methods are described in detail further down. (<a href="MDC-2" title="MDC-2">MDC-2</a> is also the name of a hash function patented by <a href="IBM" title="IBM">IBM</a>.)
</p><p>Another method is <b>2BOW</b> (or <b>NBOW</b> in general), which is a "high-rate multi-block-length hash function based on block ciphers"<sup id="cite_ref-:0_1-1" class="reference"><a href="#cite_note-:0-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup> and typically achieves (asymptotic) rates between 1 and 2 independent of the hash size (only with small constant overhead). This method has not yet seen any serious security analysis, so should be handled with care.
</p>
<meta property="mw:PageProp/toc">
<div class="mw-heading mw-heading2"><h2 id="Compression">Compression</h2></div>
<p>A compression function mixes two fixed length inputs and produces a single fixed length output of the same size as one of the inputs. This can also be seen as that the compression function transforms one large fixed-length input into a shorter, fixed-length output.
</p><p>For instance, <i>input A</i> might be 128 bits, <i>input B</i> 128 bits and they are compressed together to a single output of 128 bits. This is equivalent to having a single 256-bit input compressed to a single output of 128 bits.
</p><p>Some compression functions do not compress by half, but instead by some other factor. For example, <i>input A</i> might be 256 bits, and <i>input B</i> 128 bits, which are compressed to a single output of 128 bits. That is, a total of 384 input bits are compressed together to 128 output bits.
</p><p>The mixing is done in such a way that full <a href="Avalanche_effect" title="Avalanche effect">avalanche effect</a> is achieved. That is, every output bit depends on every input bit.
</p>
<div class="mw-heading mw-heading2"><h2 id="One-way">One-way</h2></div>
<style data-mw-deduplicate="TemplateStyles:r1236090951">
/* start https://en.wikipedia.org/ */
.mw-parser-output .hatnote{font-style:italic}.mw-parser-output div.hatnote{padding-left:1.6em;margin-bottom:0.5em}.mw-parser-output .hatnote i{font-style:normal}.mw-parser-output .hatnote+link+.hatnote{margin-top:-0.5em}@media print{body.ns-0 .mw-parser-output .hatnote{display:none!important}}
/* end https://en.wikipedia.org/ */
</style><div role="note" class="hatnote navigation-not-searchable">Main article: <a href="One-way_function" title="One-way function">one-way function</a></div>
<p>A <a href="One-way_function" title="One-way function">one-way function</a> is a function that is easy to compute but hard to invert. A one-way compression function (also called hash function) should have the following properties:
</p>
<ul><li>Easy to compute: If you have some input(s), it is easy to calculate the output.</li>
<li>Preimage-resistance: If an attacker only knows the output it should be infeasible to calculate an input. In other words, given an output <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle h}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>h</mi>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle h}</annotation>
</semantics>
</math></span><img src="./b26be3e694314bc90c3215047e4a2010c6ee184a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.339ex; height:2.176ex;" alt="{\displaystyle h}" loading="lazy"></span>, it should be unfeasible to calculate an input <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle m}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>m</mi>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle m}</annotation>
</semantics>
</math></span><img src="./0a07d98bb302f3856cbabc47b2b9016692e3f7bc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.04ex; height:1.676ex;" alt="{\displaystyle m}" loading="lazy"></span> such that <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \operatorname {hash} (m)=h}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>hash</mi>
<mo><!-- --></mo>
<mo stretchy="false">(</mo>
<mi>m</mi>
<mo stretchy="false">)</mo>
<mo>=</mo>
<mi>h</mi>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle \operatorname {hash} (m)=h}</annotation>
</semantics>
</math></span><img src="./464108f9be69db95ca0f7eb35e9a77310b0725c2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:12.951ex; height:2.843ex;" alt="{\displaystyle \operatorname {hash} (m)=h}" loading="lazy"></span>.</li>
<li>Second preimage-resistance: Given an input <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle m_{1}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<msub>
<mi>m</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>1</mn>
</mrow>
</msub>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle m_{1}}</annotation>
</semantics>
</math></span><img src="./31aafa60e48d39ccce922404c0b80340b2cc777a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:3.095ex; height:2.009ex;" alt="{\displaystyle m_{1}}" loading="lazy"></span> whose output is <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle h}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>h</mi>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle h}</annotation>
</semantics>
</math></span><img src="./b26be3e694314bc90c3215047e4a2010c6ee184a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.339ex; height:2.176ex;" alt="{\displaystyle h}" loading="lazy"></span>, it should be infeasible to find another input <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle m_{2}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<msub>
<mi>m</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>2</mn>
</mrow>
</msub>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle m_{2}}</annotation>
</semantics>
</math></span><img src="./0ecebe334d5cadc3ffcf245eb02919034d7a2ec8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:3.095ex; height:2.009ex;" alt="{\displaystyle m_{2}}" loading="lazy"></span> that has the same output <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle h}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>h</mi>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle h}</annotation>
</semantics>
</math></span><img src="./b26be3e694314bc90c3215047e4a2010c6ee184a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.339ex; height:2.176ex;" alt="{\displaystyle h}" loading="lazy"></span>, i.e. <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \operatorname {hash} (m_{1})=\operatorname {hash} (m_{2})}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>hash</mi>
<mo><!-- --></mo>
<mo stretchy="false">(</mo>
<msub>
<mi>m</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>1</mn>
</mrow>
</msub>
<mo stretchy="false">)</mo>
<mo>=</mo>
<mi>hash</mi>
<mo><!-- --></mo>
<mo stretchy="false">(</mo>
<msub>
<mi>m</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>2</mn>
</mrow>
</msub>
<mo stretchy="false">)</mo>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle \operatorname {hash} (m_{1})=\operatorname {hash} (m_{2})}</annotation>
</semantics>
</math></span><img src="./20df0ccce6e1b89024998c9376a44cbb33d4cc38.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:22.234ex; height:2.843ex;" alt="{\displaystyle \operatorname {hash} (m_{1})=\operatorname {hash} (m_{2})}" loading="lazy"></span>.</li>
<li><a href="Collision_resistance" title="Collision resistance">Collision-resistance:</a> It should be hard to find any two different inputs that compress to the same output i.e. an attacker should not be able to find a pair of messages <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle m_{1}\neq m_{2}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<msub>
<mi>m</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>1</mn>
</mrow>
</msub>
<mo>≠<!-- ≠ --></mo>
<msub>
<mi>m</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>2</mn>
</mrow>
</msub>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle m_{1}\neq m_{2}}</annotation>
</semantics>
</math></span><img src="./aca69db0a36c8c24a0edfa87036843958019baa4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.288ex; height:2.676ex;" alt="{\displaystyle m_{1}\neq m_{2}}" loading="lazy"></span> such that <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \operatorname {hash} (m_{1})=\operatorname {hash} (m_{2})}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>hash</mi>
<mo><!-- --></mo>
<mo stretchy="false">(</mo>
<msub>
<mi>m</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>1</mn>
</mrow>
</msub>
<mo stretchy="false">)</mo>
<mo>=</mo>
<mi>hash</mi>
<mo><!-- --></mo>
<mo stretchy="false">(</mo>
<msub>
<mi>m</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>2</mn>
</mrow>
</msub>
<mo stretchy="false">)</mo>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle \operatorname {hash} (m_{1})=\operatorname {hash} (m_{2})}</annotation>
</semantics>
</math></span><img src="./20df0ccce6e1b89024998c9376a44cbb33d4cc38.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:22.234ex; height:2.843ex;" alt="{\displaystyle \operatorname {hash} (m_{1})=\operatorname {hash} (m_{2})}" loading="lazy"></span>. Due to the <a href="Birthday_problem" title="Birthday problem">birthday paradox</a> (see also <a href="Birthday_attack" title="Birthday attack">birthday attack</a>) there is a 50% chance a collision can be found in time of about <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 2^{n/2}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<msup>
<mn>2</mn>
<mrow class="MJX-TeXAtom-ORD">
<mi>n</mi>
<mrow class="MJX-TeXAtom-ORD">
<mo>/</mo>
</mrow>
<mn>2</mn>
</mrow>
</msup>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle 2^{n/2}}</annotation>
</semantics>
</math></span><img src="./fd18d146490780241da66ffee2950a5f13cf6469.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:4.025ex; height:2.843ex;" alt="{\displaystyle 2^{n/2}}" loading="lazy"></span> where <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>n</mi>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle n}</annotation>
</semantics>
</math></span><img src="./a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"></span> is the number of bits in the hash function's output. An attack on the hash function thus should not be able to find a collision with less than about <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 2^{n/2}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<msup>
<mn>2</mn>
<mrow class="MJX-TeXAtom-ORD">
<mi>n</mi>
<mrow class="MJX-TeXAtom-ORD">
<mo>/</mo>
</mrow>
<mn>2</mn>
</mrow>
</msup>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle 2^{n/2}}</annotation>
</semantics>
</math></span><img src="./fd18d146490780241da66ffee2950a5f13cf6469.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:4.025ex; height:2.843ex;" alt="{\displaystyle 2^{n/2}}" loading="lazy"></span> work.</li></ul>
<p>Ideally one would like the "infeasibility" in preimage-resistance and second preimage-resistance to mean a work of about <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 2^{n}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<msup>
<mn>2</mn>
<mrow class="MJX-TeXAtom-ORD">
<mi>n</mi>
</mrow>
</msup>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle 2^{n}}</annotation>
</semantics>
</math></span><img src="./8226f30650ee4fe4e640c6d2798127e80e9c160d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.381ex; height:2.343ex;" alt="{\displaystyle 2^{n}}" loading="lazy"></span> where <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>n</mi>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle n}</annotation>
</semantics>
</math></span><img src="./a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"></span> is the number of bits in the hash function's output. However, particularly for second preimage-resistance this is a difficult problem.
</p>
<div class="mw-heading mw-heading2"><h2 id="The_Merkle–Damgård_construction">The Merkle–Damgård construction</h2></div>
<div role="note" class="hatnote navigation-not-searchable">Main article: <a href="Merkle%E2%80%93Damg%C3%A5rd_construction" title="Merkle–Damgård construction">Merkle–Damgård construction</a></div>
<p>A common use of one-way compression functions is in the Merkle–Damgård construction inside cryptographic hash functions. Most widely used hash functions, including <a href="MD5" title="MD5">MD5</a>, <a href="SHA-1" title="SHA-1">SHA-1</a> (which is deprecated<sup id="cite_ref-2" class="reference"><a href="#cite_note-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup>) and <a href="SHA-2" title="SHA-2">SHA-2</a> use this construction.
</p><p>A hash function must be able to process an arbitrary-length message into a fixed-length output. This can be achieved by breaking the input up into a series of equal-sized blocks, and operating on them in sequence using a one-way compression function. The compression function can either be specially designed for hashing or be built from a block cipher. The last block processed should also be <a href="Padding_(cryptography)" title="Padding (cryptography)">length padded</a>, which is crucial to the security of this construction.
</p><p>When length padding (also called MD-strengthening) is applied, attacks cannot find collisions faster than the birthday paradox (<span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 2^{n/2}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<msup>
<mn>2</mn>
<mrow class="MJX-TeXAtom-ORD">
<mi>n</mi>
<mrow class="MJX-TeXAtom-ORD">
<mo>/</mo>
</mrow>
<mn>2</mn>
</mrow>
</msup>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle 2^{n/2}}</annotation>
</semantics>
</math></span><img src="./fd18d146490780241da66ffee2950a5f13cf6469.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:4.025ex; height:2.843ex;" alt="{\displaystyle 2^{n/2}}" loading="lazy"></span>, <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>n</mi>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle n}</annotation>
</semantics>
</math></span><img src="./a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"></span> being the block size in bits) if the used function <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>f</mi>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle f}</annotation>
</semantics>
</math></span><img src="./132e57acb643253e7810ee9702d9581f159a1c61.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.279ex; height:2.509ex;" alt="{\displaystyle f}" loading="lazy"></span> is collision-resistant.<sup id="cite_ref-damgard89_3-0" class="reference"><a href="#cite_note-damgard89-3"><span class="cite-bracket">[</span>3<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-merkle89_4-0" class="reference"><a href="#cite_note-merkle89-4"><span class="cite-bracket">[</span>4<span class="cite-bracket">]</span></a></sup> Hence, the Merkle–Damgård hash construction reduces the problem of finding a proper hash function to finding a proper compression function.
</p><p>A second preimage attack (given a message <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle m_{1}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<msub>
<mi>m</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>1</mn>
</mrow>
</msub>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle m_{1}}</annotation>
</semantics>
</math></span><img src="./31aafa60e48d39ccce922404c0b80340b2cc777a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:3.095ex; height:2.009ex;" alt="{\displaystyle m_{1}}" loading="lazy"></span> an attacker finds another message <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle m_{2}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<msub>
<mi>m</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>2</mn>
</mrow>
</msub>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle m_{2}}</annotation>
</semantics>
</math></span><img src="./0ecebe334d5cadc3ffcf245eb02919034d7a2ec8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:3.095ex; height:2.009ex;" alt="{\displaystyle m_{2}}" loading="lazy"></span> to satisfy <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \operatorname {hash} (m_{1})=\operatorname {hash} (m_{2})}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>hash</mi>
<mo><!-- --></mo>
<mo stretchy="false">(</mo>
<msub>
<mi>m</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>1</mn>
</mrow>
</msub>
<mo stretchy="false">)</mo>
<mo>=</mo>
<mi>hash</mi>
<mo><!-- --></mo>
<mo stretchy="false">(</mo>
<msub>
<mi>m</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>2</mn>
</mrow>
</msub>
<mo stretchy="false">)</mo>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle \operatorname {hash} (m_{1})=\operatorname {hash} (m_{2})}</annotation>
</semantics>
</math></span><img src="./20df0ccce6e1b89024998c9376a44cbb33d4cc38.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:22.234ex; height:2.843ex;" alt="{\displaystyle \operatorname {hash} (m_{1})=\operatorname {hash} (m_{2})}" loading="lazy"></span> can be done according to Kelsey and Schneier<sup id="cite_ref-ks05_5-0" class="reference"><a href="#cite_note-ks05-5"><span class="cite-bracket">[</span>5<span class="cite-bracket">]</span></a></sup> for a <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 2^{k}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<msup>
<mn>2</mn>
<mrow class="MJX-TeXAtom-ORD">
<mi>k</mi>
</mrow>
</msup>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle 2^{k}}</annotation>
</semantics>
</math></span><img src="./2d82641ae2702b0db07dd11830af27b9ee0cd196.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.251ex; height:2.676ex;" alt="{\displaystyle 2^{k}}" loading="lazy"></span>-message-block message in time <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k\times 2^{n/2+1}+2^{n-k+1}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>k</mi>
<mo>×<!-- × --></mo>
<msup>
<mn>2</mn>
<mrow class="MJX-TeXAtom-ORD">
<mi>n</mi>
<mrow class="MJX-TeXAtom-ORD">
<mo>/</mo>
</mrow>
<mn>2</mn>
<mo>+</mo>
<mn>1</mn>
</mrow>
</msup>
<mo>+</mo>
<msup>
<mn>2</mn>
<mrow class="MJX-TeXAtom-ORD">
<mi>n</mi>
<mo>−<!-- − --></mo>
<mi>k</mi>
<mo>+</mo>
<mn>1</mn>
</mrow>
</msup>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle k\times 2^{n/2+1}+2^{n-k+1}}</annotation>
</semantics>
</math></span><img src="./b023b5f0466256520b0f97f4c4a8fc6282f021ca.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:19.634ex; height:3.009ex;" alt="{\displaystyle k\times 2^{n/2+1}+2^{n-k+1}}" loading="lazy"></span>. The complexity of this attack reaches a minimum of <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 2^{3n/4+2}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<msup>
<mn>2</mn>
<mrow class="MJX-TeXAtom-ORD">
<mn>3</mn>
<mi>n</mi>
<mrow class="MJX-TeXAtom-ORD">
<mo>/</mo>
</mrow>
<mn>4</mn>
<mo>+</mo>
<mn>2</mn>
</mrow>
</msup>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle 2^{3n/4+2}}</annotation>
</semantics>
</math></span><img src="./e08ac1773f58a5baa27260f3b32329310624ca6a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:6.947ex; height:2.843ex;" alt="{\displaystyle 2^{3n/4+2}}" loading="lazy"></span> for long messages when <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k=2^{n/4}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>k</mi>
<mo>=</mo>
<msup>
<mn>2</mn>
<mrow class="MJX-TeXAtom-ORD">
<mi>n</mi>
<mrow class="MJX-TeXAtom-ORD">
<mo>/</mo>
</mrow>
<mn>4</mn>
</mrow>
</msup>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle k=2^{n/4}}</annotation>
</semantics>
</math></span><img src="./d6224245a7b26fb89b26249b596b58cd1f7545a6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:8.335ex; height:2.843ex;" alt="{\displaystyle k=2^{n/4}}" loading="lazy"></span> and approaches <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 2^{n}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<msup>
<mn>2</mn>
<mrow class="MJX-TeXAtom-ORD">
<mi>n</mi>
</mrow>
</msup>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle 2^{n}}</annotation>
</semantics>
</math></span><img src="./8226f30650ee4fe4e640c6d2798127e80e9c160d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.381ex; height:2.343ex;" alt="{\displaystyle 2^{n}}" loading="lazy"></span> when messages are short.
</p>
<div style="clear:both;" class=""></div>
<div class="mw-heading mw-heading2"><h2 id="Construction_from_block_ciphers">Construction from block ciphers</h2></div>
<p>One-way compression functions are often built from block ciphers.
</p><p>Block ciphers take (like one-way compression functions) two fixed size inputs (the <a href="Key_(cryptography)" title="Key (cryptography)">key</a> and the <a href="Plaintext" title="Plaintext">plaintext</a>) and return one single output (the <a href="Ciphertext" title="Ciphertext">ciphertext</a>) which is the same size as the input plaintext.
</p><p>However, modern block ciphers are only partially one-way. That is, given a plaintext and a ciphertext it is infeasible to find a key that encrypts the plaintext to the ciphertext. But, given a ciphertext and a key a matching plaintext can be found simply by using the block cipher's decryption function. Thus, to turn a block cipher into a one-way compression function some extra operations have to be added.
</p><p>Some methods to turn any normal block cipher into a one-way compression function are Davies–Meyer, Matyas–Meyer–Oseas, Miyaguchi–Preneel (single-block-length compression functions) and MDC-2, MDC-4, Hirose (double-block-length compressions functions).
</p><p>Single-block-length compression functions output the same number of bits as processed by the underlying block cipher. Consequently, double-block-length compression functions output twice the number of bits.
</p><p>If a block cipher has a <a href="Block_size_(cryptography)" title="Block size (cryptography)">block size</a> of say 128 bits single-block-length methods create a hash function that has the block size of 128 bits and produces a hash of 128 bits. Double-block-length methods make hashes with double the hash size compared to the block size of the block cipher used. So a 128-bit block cipher can be turned into a 256-bit hash function.
</p><p>These methods are then used inside the Merkle–Damgård construction to build the actual hash function. These methods are described in detail further down.
</p><p>Using a block cipher to build the one-way compression function for a hash function is usually somewhat slower than using a specially designed one-way compression function in the hash function. This is because all known secure constructions do the <a href="Key_schedule" title="Key schedule">key scheduling</a> for each block of the message. Black, Cochran and Shrimpton have shown that it is impossible to construct a one-way compression function that makes only one call to a block cipher with a fixed key.<sup id="cite_ref-6" class="reference"><a href="#cite_note-6"><span class="cite-bracket">[</span>6<span class="cite-bracket">]</span></a></sup> In practice reasonable speeds are achieved provided the key scheduling of the selected block cipher is not a too heavy operation.
</p><p>But, in some cases it is easier because a single implementation of a block cipher can be used for both a block cipher and a hash function. It can also save <a href="Machine_code" title="Machine code">code</a> space in very tiny <a href="Embedded_system" title="Embedded system">embedded systems</a> like for instance <a href="Smart_card" title="Smart card">smart cards</a> or <a href="Electronic_control_unit" title="Electronic control unit">nodes in cars</a> or other machines.
</p><p>Therefore, the hash-rate or rate gives a glimpse of the efficiency of a hash function based on a certain compression function. The rate of an iterated hash function outlines the ratio between the number of block cipher operations and the output. More precisely, the rate represents the ratio between the number of processed bits of input <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle m}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>m</mi>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle m}</annotation>
</semantics>
</math></span><img src="./0a07d98bb302f3856cbabc47b2b9016692e3f7bc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.04ex; height:1.676ex;" alt="{\displaystyle m}" loading="lazy"></span>, the output bit-length <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>n</mi>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle n}</annotation>
</semantics>
</math></span><img src="./a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"></span> of the block cipher, and the necessary block cipher operations <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle s}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>s</mi>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle s}</annotation>
</semantics>
</math></span><img src="./01d131dfd7673938b947072a13a9744fe997e632.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.09ex; height:1.676ex;" alt="{\displaystyle s}" loading="lazy"></span> to produce these <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>n</mi>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle n}</annotation>
</semantics>
</math></span><img src="./a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"></span> output bits. Generally, the usage of fewer block cipher operations results in a better overall performance of the entire hash function, but it also leads to a smaller hash-value which could be undesirable. The rate is expressed by the formula:
</p><p><span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle R_{h}={\frac {\left|m_{i}\right|}{s\cdot n}}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<msub>
<mi>R</mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>h</mi>
</mrow>
</msub>
<mo>=</mo>
<mrow class="MJX-TeXAtom-ORD">
<mfrac>
<mrow>
<mo>|</mo>
<msub>
<mi>m</mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>i</mi>
</mrow>
</msub>
<mo>|</mo>
</mrow>
<mrow>
<mi>s</mi>
<mo>⋅<!-- ⋅ --></mo>
<mi>n</mi>
</mrow>
</mfrac>
</mrow>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle R_{h}={\frac {\left|m_{i}\right|}{s\cdot n}}}</annotation>
</semantics>
</math></span><img src="./3e055cb7c9ef6b87df16c5476fc86bc5d94f406c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.838ex; width:11.042ex; height:5.676ex;" alt="{\displaystyle R_{h}={\frac {\left|m_{i}\right|}{s\cdot n}}}" loading="lazy"></span>
</p><p>The hash function can only be considered secure if at least the following conditions are met:
</p>
<ul><li>The block cipher has no special properties that distinguish it from ideal ciphers, such as weak keys or keys that lead to identical or related encryptions (fixed points or key-collisions).</li>
<li>The resulting hash size is big enough. According to the <a href="Birthday_attack" title="Birthday attack">birthday attack</a> a <a href="Security_level" title="Security level">security level</a> of 2<sup>80</sup> (generally assumed to be infeasible to compute today) is desirable thus the hash size should be at least 160 bits.</li>
<li>The last block is properly length padded prior to the hashing. (See <a href="Merkle%E2%80%93Damg%C3%A5rd_construction" title="Merkle–Damgård construction">Merkle–Damgård construction</a>.) Length padding is normally implemented and handled internally in specialised hash functions like <a href="SHA-1" title="SHA-1">SHA-1</a> etc.</li></ul>
<p>The constructions presented below: Davies–Meyer, Matyas–Meyer–Oseas, Miyaguchi–Preneel and Hirose have been shown to be secure under the <a href="Black-box" class="mw-redirect" title="Black-box">black-box</a> analysis.<sup id="cite_ref-7" class="reference"><a href="#cite_note-7"><span class="cite-bracket">[</span>7<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-Hirose06_8-0" class="reference"><a href="#cite_note-Hirose06-8"><span class="cite-bracket">[</span>8<span class="cite-bracket">]</span></a></sup> The goal is to show that any attack that can be found is at most as efficient as the <a href="Birthday_attack" title="Birthday attack">birthday attack</a> under certain assumptions. The black-box model assumes that a block cipher is used that is randomly chosen from a set containing all appropriate block ciphers. In this model an attacker may freely encrypt and decrypt any blocks, but does not have access to an implementation of the block cipher. The encryption and decryption function are represented by oracles that receive a pair of either a plaintext and a key or a ciphertext and a key. The oracles then respond with a randomly chosen plaintext or ciphertext, if the pair was asked for the first time. They both share a table for these triplets, a pair from the query and corresponding response, and return the record, if a query was received for the second time. For the proof there is a collision finding algorithm that makes randomly chosen queries to the oracles. The algorithm returns 1, if two responses result in a collision involving the hash function that is built from a compression function applying this block cipher (0 else). The probability that the algorithm returns 1 is dependent on the number of queries which determine the security level.
</p>
<div class="mw-heading mw-heading2"><h2 id="Davies–Meyer">Davies–Meyer</h2></div>
<p>The Davies–Meyer single-block-length compression function feeds each block of the message (<span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle m_{i}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<msub>
<mi>m</mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>i</mi>
</mrow>
</msub>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle m_{i}}</annotation>
</semantics>
</math></span><img src="./95ec8e804f69706d3f5ad235f4f983220c8df7c2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.84ex; height:2.009ex;" alt="{\displaystyle m_{i}}" loading="lazy"></span>) as the key to a block cipher. It feeds the previous hash value (<span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle H_{i-1}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<msub>
<mi>H</mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>i</mi>
<mo>−<!-- − --></mo>
<mn>1</mn>
</mrow>
</msub>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle H_{i-1}}</annotation>
</semantics>
</math></span><img src="./82bfb2b5eaa0f531b23e9f17f7e0ed31c89a8e76.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:4.831ex; height:2.509ex;" alt="{\displaystyle H_{i-1}}" loading="lazy"></span>) as the plaintext to be encrypted. The output ciphertext is then also <a href="Exclusive-or" class="mw-redirect" title="Exclusive-or">XORed</a> (⊕) with the previous hash value (<span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle H_{i-1}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<msub>
<mi>H</mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>i</mi>
<mo>−<!-- − --></mo>
<mn>1</mn>
</mrow>
</msub>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle H_{i-1}}</annotation>
</semantics>
</math></span><img src="./82bfb2b5eaa0f531b23e9f17f7e0ed31c89a8e76.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:4.831ex; height:2.509ex;" alt="{\displaystyle H_{i-1}}" loading="lazy"></span>) to produce the next hash value (<span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle H_{i}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<msub>
<mi>H</mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>i</mi>
</mrow>
</msub>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle H_{i}}</annotation>
</semantics>
</math></span><img src="./7bd0312f590cc5a400008938f3cc304d42ad3986.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.731ex; height:2.509ex;" alt="{\displaystyle H_{i}}" loading="lazy"></span>). In the first round when there is no previous hash value it uses a constant pre-specified initial value (<span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle H_{0}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<msub>
<mi>H</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>0</mn>
</mrow>
</msub>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle H_{0}}</annotation>
</semantics>
</math></span><img src="./43910602a221b7a4c373791f94793e3008622070.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.985ex; height:2.509ex;" alt="{\displaystyle H_{0}}" loading="lazy"></span>).
</p><p>In <a href="Mathematical_notation" title="Mathematical notation">mathematical notation</a> Davies–Meyer can be described as:
</p>
<dl><dd><span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle H_{i}=E_{m_{i}}{(H_{i-1})}\oplus {H_{i-1}}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<msub>
<mi>H</mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>i</mi>
</mrow>
</msub>
<mo>=</mo>
<msub>
<mi>E</mi>
<mrow class="MJX-TeXAtom-ORD">
<msub>
<mi>m</mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>i</mi>
</mrow>
</msub>
</mrow>
</msub>
<mrow class="MJX-TeXAtom-ORD">
<mo stretchy="false">(</mo>
<msub>
<mi>H</mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>i</mi>
<mo>−<!-- − --></mo>
<mn>1</mn>
</mrow>
</msub>
<mo stretchy="false">)</mo>
</mrow>
<mo>⊕<!-- ⊕ --></mo>
<mrow class="MJX-TeXAtom-ORD">
<msub>
<mi>H</mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>i</mi>
<mo>−<!-- − --></mo>
<mn>1</mn>
</mrow>
</msub>
</mrow>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle H_{i}=E_{m_{i}}{(H_{i-1})}\oplus {H_{i-1}}}</annotation>
</semantics>
</math></span><img src="./ba2ad4e39d628ba2e1ad6fca8df24473b307cce6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:24.157ex; height:3.009ex;" alt="{\displaystyle H_{i}=E_{m_{i}}{(H_{i-1})}\oplus {H_{i-1}}}" loading="lazy"></span></dd></dl>
<p>The scheme has the rate (k is the keysize):
</p>
<dl><dd><span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle R_{DM}={\frac {k}{1\cdot n}}={\frac {k}{n}}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<msub>
<mi>R</mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>D</mi>
<mi>M</mi>
</mrow>
</msub>
<mo>=</mo>
<mrow class="MJX-TeXAtom-ORD">
<mfrac>
<mi>k</mi>
<mrow>
<mn>1</mn>
<mo>⋅<!-- ⋅ --></mo>
<mi>n</mi>
</mrow>
</mfrac>
</mrow>
<mo>=</mo>
<mrow class="MJX-TeXAtom-ORD">
<mfrac>
<mi>k</mi>
<mi>n</mi>
</mfrac>
</mrow>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle R_{DM}={\frac {k}{1\cdot n}}={\frac {k}{n}}}</annotation>
</semantics>
</math></span><img src="./faa03e46e4c18db765d6fbfaf61cdc879cc5b55b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.838ex; width:18.584ex; height:5.343ex;" alt="{\displaystyle R_{DM}={\frac {k}{1\cdot n}}={\frac {k}{n}}}" loading="lazy"></span></dd></dl>
<p>If the block cipher uses for instance 256-bit keys then each message block (<span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle m_{i}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<msub>
<mi>m</mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>i</mi>
</mrow>
</msub>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle m_{i}}</annotation>
</semantics>
</math></span><img src="./95ec8e804f69706d3f5ad235f4f983220c8df7c2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.84ex; height:2.009ex;" alt="{\displaystyle m_{i}}" loading="lazy"></span>) is a 256-bit chunk of the message. If the same block cipher uses a block size of 128 bits then the input and output hash values in each round is 128 bits.
</p><p>Variations of this method replace XOR with any other group operation, such as addition on 32-bit unsigned integers.
</p><p>A notable property of the Davies–Meyer construction is that even if the underlying block cipher is totally secure, it is possible to compute <a href="Fixed_point_(mathematics)" title="Fixed point (mathematics)">fixed points</a> for the construction: for any <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle m}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>m</mi>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle m}</annotation>
</semantics>
</math></span><img src="./0a07d98bb302f3856cbabc47b2b9016692e3f7bc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.04ex; height:1.676ex;" alt="{\displaystyle m}" loading="lazy"></span>, one can find a value of <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle h}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>h</mi>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle h}</annotation>
</semantics>
</math></span><img src="./b26be3e694314bc90c3215047e4a2010c6ee184a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.339ex; height:2.176ex;" alt="{\displaystyle h}" loading="lazy"></span> such that <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle E_{m}(h)\oplus h=h}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<msub>
<mi>E</mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>m</mi>
</mrow>
</msub>
<mo stretchy="false">(</mo>
<mi>h</mi>
<mo stretchy="false">)</mo>
<mo>⊕<!-- ⊕ --></mo>
<mi>h</mi>
<mo>=</mo>
<mi>h</mi>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle E_{m}(h)\oplus h=h}</annotation>
</semantics>
</math></span><img src="./2b82b001e963332fbda9a3b80cd7076196a60175.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:15.155ex; height:2.843ex;" alt="{\displaystyle E_{m}(h)\oplus h=h}" loading="lazy"></span>: one just has to set <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle h=E_{m}^{-1}(0)}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>h</mi>
<mo>=</mo>
<msubsup>
<mi>E</mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>m</mi>
</mrow>
<mrow class="MJX-TeXAtom-ORD">
<mo>−<!-- − --></mo>
<mn>1</mn>
</mrow>
</msubsup>
<mo stretchy="false">(</mo>
<mn>0</mn>
<mo stretchy="false">)</mo>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle h=E_{m}^{-1}(0)}</annotation>
</semantics>
</math></span><img src="./4a4b797d240206dbaf2cffcc81f9bd861527f24d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:11.536ex; height:3.176ex;" alt="{\displaystyle h=E_{m}^{-1}(0)}" loading="lazy"></span>.<sup id="cite_ref-9" class="reference"><a href="#cite_note-9"><span class="cite-bracket">[</span>9<span class="cite-bracket">]</span></a></sup> This is a property that <a href="Random_function" class="mw-redirect" title="Random function">random functions</a> certainly do not have. So far, no practical attack has been based on this property, but one should be aware of this "feature". The fixed-points can be used in a second preimage attack (given a message <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle m_{1}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<msub>
<mi>m</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>1</mn>
</mrow>
</msub>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle m_{1}}</annotation>
</semantics>
</math></span><img src="./31aafa60e48d39ccce922404c0b80340b2cc777a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:3.095ex; height:2.009ex;" alt="{\displaystyle m_{1}}" loading="lazy"></span>, attacker finds another message <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle m_{2}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<msub>
<mi>m</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>2</mn>
</mrow>
</msub>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle m_{2}}</annotation>
</semantics>
</math></span><img src="./0ecebe334d5cadc3ffcf245eb02919034d7a2ec8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:3.095ex; height:2.009ex;" alt="{\displaystyle m_{2}}" loading="lazy"></span> to satisfy <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \operatorname {hash} (m_{1})=\operatorname {hash} (m_{2})}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>hash</mi>
<mo><!-- --></mo>
<mo stretchy="false">(</mo>
<msub>
<mi>m</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>1</mn>
</mrow>
</msub>
<mo stretchy="false">)</mo>
<mo>=</mo>
<mi>hash</mi>
<mo><!-- --></mo>
<mo stretchy="false">(</mo>
<msub>
<mi>m</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>2</mn>
</mrow>
</msub>
<mo stretchy="false">)</mo>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle \operatorname {hash} (m_{1})=\operatorname {hash} (m_{2})}</annotation>
</semantics>
</math></span><img src="./20df0ccce6e1b89024998c9376a44cbb33d4cc38.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:22.234ex; height:2.843ex;" alt="{\displaystyle \operatorname {hash} (m_{1})=\operatorname {hash} (m_{2})}" loading="lazy"></span>) of Kelsey and Schneier <sup id="cite_ref-ks05_5-1" class="reference"><a href="#cite_note-ks05-5"><span class="cite-bracket">[</span>5<span class="cite-bracket">]</span></a></sup> for a <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 2^{k}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<msup>
<mn>2</mn>
<mrow class="MJX-TeXAtom-ORD">
<mi>k</mi>
</mrow>
</msup>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle 2^{k}}</annotation>
</semantics>
</math></span><img src="./2d82641ae2702b0db07dd11830af27b9ee0cd196.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.251ex; height:2.676ex;" alt="{\displaystyle 2^{k}}" loading="lazy"></span>-message-block message in time <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 3\times 2^{n/2+1}+2^{n-k+1}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mn>3</mn>
<mo>×<!-- × --></mo>
<msup>
<mn>2</mn>
<mrow class="MJX-TeXAtom-ORD">
<mi>n</mi>
<mrow class="MJX-TeXAtom-ORD">
<mo>/</mo>
</mrow>
<mn>2</mn>
<mo>+</mo>
<mn>1</mn>
</mrow>
</msup>
<mo>+</mo>
<msup>
<mn>2</mn>
<mrow class="MJX-TeXAtom-ORD">
<mi>n</mi>
<mo>−<!-- − --></mo>
<mi>k</mi>
<mo>+</mo>
<mn>1</mn>
</mrow>
</msup>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle 3\times 2^{n/2+1}+2^{n-k+1}}</annotation>
</semantics>
</math></span><img src="./a91ab572b864ecebf2d9e734d51a7360d7d15684.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:19.585ex; height:3.009ex;" alt="{\displaystyle 3\times 2^{n/2+1}+2^{n-k+1}}" loading="lazy"></span>. If the construction does not allow easy creation of fixed points (like Matyas–Meyer–Oseas or Miyaguchi–Preneel) then this attack can be done in <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k\times 2^{n/2+1}+2^{n-k+1}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>k</mi>
<mo>×<!-- × --></mo>
<msup>
<mn>2</mn>
<mrow class="MJX-TeXAtom-ORD">
<mi>n</mi>
<mrow class="MJX-TeXAtom-ORD">
<mo>/</mo>
</mrow>
<mn>2</mn>
<mo>+</mo>
<mn>1</mn>
</mrow>
</msup>
<mo>+</mo>
<msup>
<mn>2</mn>
<mrow class="MJX-TeXAtom-ORD">
<mi>n</mi>
<mo>−<!-- − --></mo>
<mi>k</mi>
<mo>+</mo>
<mn>1</mn>
</mrow>
</msup>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle k\times 2^{n/2+1}+2^{n-k+1}}</annotation>
</semantics>
</math></span><img src="./b023b5f0466256520b0f97f4c4a8fc6282f021ca.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:19.634ex; height:3.009ex;" alt="{\displaystyle k\times 2^{n/2+1}+2^{n-k+1}}" loading="lazy"></span> time. In both cases the complexity is above <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 2^{n/2}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<msup>
<mn>2</mn>
<mrow class="MJX-TeXAtom-ORD">
<mi>n</mi>
<mrow class="MJX-TeXAtom-ORD">
<mo>/</mo>
</mrow>
<mn>2</mn>
</mrow>
</msup>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle 2^{n/2}}</annotation>
</semantics>
</math></span><img src="./fd18d146490780241da66ffee2950a5f13cf6469.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:4.025ex; height:2.843ex;" alt="{\displaystyle 2^{n/2}}" loading="lazy"></span> but below <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 2^{n}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<msup>
<mn>2</mn>
<mrow class="MJX-TeXAtom-ORD">
<mi>n</mi>
</mrow>
</msup>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle 2^{n}}</annotation>
</semantics>
</math></span><img src="./8226f30650ee4fe4e640c6d2798127e80e9c160d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.381ex; height:2.343ex;" alt="{\displaystyle 2^{n}}" loading="lazy"></span> when messages are long and that when messages get shorter the complexity of the attack approaches <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 2^{n}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<msup>
<mn>2</mn>
<mrow class="MJX-TeXAtom-ORD">
<mi>n</mi>
</mrow>
</msup>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle 2^{n}}</annotation>
</semantics>
</math></span><img src="./8226f30650ee4fe4e640c6d2798127e80e9c160d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.381ex; height:2.343ex;" alt="{\displaystyle 2^{n}}" loading="lazy"></span>.
</p><p>The security of the Davies–Meyer construction in the Ideal Cipher Model was first proven by R. Winternitz.<sup id="cite_ref-10" class="reference"><a href="#cite_note-10"><span class="cite-bracket">[</span>10<span class="cite-bracket">]</span></a></sup>
</p>
<div style="clear:both;" class=""></div>
<div class="mw-heading mw-heading2"><h2 id="Matyas–Meyer–Oseas">Matyas–Meyer–Oseas</h2></div>
<p>The Matyas–Meyer–Oseas single-block-length one-way compression function can be considered the dual (the opposite) of Davies–Meyer.
</p><p>It feeds each block of the message (<span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle m_{i}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<msub>
<mi>m</mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>i</mi>
</mrow>
</msub>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle m_{i}}</annotation>
</semantics>
</math></span><img src="./95ec8e804f69706d3f5ad235f4f983220c8df7c2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.84ex; height:2.009ex;" alt="{\displaystyle m_{i}}" loading="lazy"></span>) as the plaintext to be encrypted. The output ciphertext is then also XORed (⊕) with the same message block (<span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle m_{i}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<msub>
<mi>m</mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>i</mi>
</mrow>
</msub>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle m_{i}}</annotation>
</semantics>
</math></span><img src="./95ec8e804f69706d3f5ad235f4f983220c8df7c2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.84ex; height:2.009ex;" alt="{\displaystyle m_{i}}" loading="lazy"></span>) to produce the next hash value (<span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle H_{i}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<msub>
<mi>H</mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>i</mi>
</mrow>
</msub>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle H_{i}}</annotation>
</semantics>
</math></span><img src="./7bd0312f590cc5a400008938f3cc304d42ad3986.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.731ex; height:2.509ex;" alt="{\displaystyle H_{i}}" loading="lazy"></span>). The previous hash value (<span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle H_{i-1}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<msub>
<mi>H</mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>i</mi>
<mo>−<!-- − --></mo>
<mn>1</mn>
</mrow>
</msub>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle H_{i-1}}</annotation>
</semantics>
</math></span><img src="./82bfb2b5eaa0f531b23e9f17f7e0ed31c89a8e76.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:4.831ex; height:2.509ex;" alt="{\displaystyle H_{i-1}}" loading="lazy"></span>) is fed as the key to the block cipher. In the first round when there is no previous hash value it uses a constant pre-specified initial value (<span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle H_{0}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<msub>
<mi>H</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>0</mn>
</mrow>
</msub>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle H_{0}}</annotation>
</semantics>
</math></span><img src="./43910602a221b7a4c373791f94793e3008622070.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.985ex; height:2.509ex;" alt="{\displaystyle H_{0}}" loading="lazy"></span>).
</p><p>If the block cipher has different block and key sizes the hash value (<span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle H_{i-1}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<msub>
<mi>H</mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>i</mi>
<mo>−<!-- − --></mo>
<mn>1</mn>
</mrow>
</msub>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle H_{i-1}}</annotation>
</semantics>
</math></span><img src="./82bfb2b5eaa0f531b23e9f17f7e0ed31c89a8e76.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:4.831ex; height:2.509ex;" alt="{\displaystyle H_{i-1}}" loading="lazy"></span>) will have the wrong size for use as the key. The cipher might also have other special requirements on the key. Then the hash value is first fed through the function <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle g}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>g</mi>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle g}</annotation>
</semantics>
</math></span><img src="./d3556280e66fe2c0d0140df20935a6f057381d77.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.116ex; height:2.009ex;" alt="{\displaystyle g}" loading="lazy"></span> to be converted/padded to fit as key for the cipher.
</p><p>In mathematical notation Matyas–Meyer–Oseas can be described as:
</p>
<dl><dd><span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle H_{i}=E_{g(H_{i-1})}(m_{i})\oplus m_{i}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<msub>
<mi>H</mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>i</mi>
</mrow>
</msub>
<mo>=</mo>
<msub>
<mi>E</mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>g</mi>
<mo stretchy="false">(</mo>
<msub>
<mi>H</mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>i</mi>
<mo>−<!-- − --></mo>
<mn>1</mn>
</mrow>
</msub>
<mo stretchy="false">)</mo>
</mrow>
</msub>
<mo stretchy="false">(</mo>
<msub>
<mi>m</mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>i</mi>
</mrow>
</msub>
<mo stretchy="false">)</mo>
<mo>⊕<!-- ⊕ --></mo>
<msub>
<mi>m</mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>i</mi>
</mrow>
</msub>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle H_{i}=E_{g(H_{i-1})}(m_{i})\oplus m_{i}}</annotation>
</semantics>
</math></span><img src="./8ea15f2fc9de730a9b7ab6d3fd84d60f12fda0d2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.171ex; width:23.871ex; height:3.176ex;" alt="{\displaystyle H_{i}=E_{g(H_{i-1})}(m_{i})\oplus m_{i}}" loading="lazy"></span></dd></dl>
<p>The scheme has the rate:
</p>
<dl><dd><span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle R_{MMO}={\frac {n}{1\cdot n}}=1}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<msub>
<mi>R</mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>M</mi>
<mi>M</mi>
<mi>O</mi>
</mrow>
</msub>
<mo>=</mo>
<mrow class="MJX-TeXAtom-ORD">
<mfrac>
<mi>n</mi>
<mrow>
<mn>1</mn>
<mo>⋅<!-- ⋅ --></mo>
<mi>n</mi>
</mrow>
</mfrac>
</mrow>
<mo>=</mo>
<mn>1</mn>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle R_{MMO}={\frac {n}{1\cdot n}}=1}</annotation>
</semantics>
</math></span><img src="./6677ad27b7f206c0ef2073e1eba0cfeb17e7f445.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.838ex; width:19.136ex; height:4.676ex;" alt="{\displaystyle R_{MMO}={\frac {n}{1\cdot n}}=1}" loading="lazy"></span></dd></dl>
<p>A second preimage attack (given a message <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle m_{1}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<msub>
<mi>m</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>1</mn>
</mrow>
</msub>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle m_{1}}</annotation>
</semantics>
</math></span><img src="./31aafa60e48d39ccce922404c0b80340b2cc777a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:3.095ex; height:2.009ex;" alt="{\displaystyle m_{1}}" loading="lazy"></span> an attacker finds another message <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle m_{2}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<msub>
<mi>m</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>2</mn>
</mrow>
</msub>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle m_{2}}</annotation>
</semantics>
</math></span><img src="./0ecebe334d5cadc3ffcf245eb02919034d7a2ec8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:3.095ex; height:2.009ex;" alt="{\displaystyle m_{2}}" loading="lazy"></span> to satisfy <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \operatorname {hash} (m_{1})=\operatorname {hash} (m_{2})}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>hash</mi>
<mo><!-- --></mo>
<mo stretchy="false">(</mo>
<msub>
<mi>m</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>1</mn>
</mrow>
</msub>
<mo stretchy="false">)</mo>
<mo>=</mo>
<mi>hash</mi>
<mo><!-- --></mo>
<mo stretchy="false">(</mo>
<msub>
<mi>m</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>2</mn>
</mrow>
</msub>
<mo stretchy="false">)</mo>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle \operatorname {hash} (m_{1})=\operatorname {hash} (m_{2})}</annotation>
</semantics>
</math></span><img src="./20df0ccce6e1b89024998c9376a44cbb33d4cc38.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:22.234ex; height:2.843ex;" alt="{\displaystyle \operatorname {hash} (m_{1})=\operatorname {hash} (m_{2})}" loading="lazy"></span>) can be done according to Kelsey and Schneier<sup id="cite_ref-ks05_5-2" class="reference"><a href="#cite_note-ks05-5"><span class="cite-bracket">[</span>5<span class="cite-bracket">]</span></a></sup> for a <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 2^{k}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<msup>
<mn>2</mn>
<mrow class="MJX-TeXAtom-ORD">
<mi>k</mi>
</mrow>
</msup>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle 2^{k}}</annotation>
</semantics>
</math></span><img src="./2d82641ae2702b0db07dd11830af27b9ee0cd196.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.251ex; height:2.676ex;" alt="{\displaystyle 2^{k}}" loading="lazy"></span>-message-block message in time <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k\times 2^{n/2+1}+2^{n-k+1}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>k</mi>
<mo>×<!-- × --></mo>
<msup>
<mn>2</mn>
<mrow class="MJX-TeXAtom-ORD">
<mi>n</mi>
<mrow class="MJX-TeXAtom-ORD">
<mo>/</mo>
</mrow>
<mn>2</mn>
<mo>+</mo>
<mn>1</mn>
</mrow>
</msup>
<mo>+</mo>
<msup>
<mn>2</mn>
<mrow class="MJX-TeXAtom-ORD">
<mi>n</mi>
<mo>−<!-- − --></mo>
<mi>k</mi>
<mo>+</mo>
<mn>1</mn>
</mrow>
</msup>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle k\times 2^{n/2+1}+2^{n-k+1}}</annotation>
</semantics>
</math></span><img src="./b023b5f0466256520b0f97f4c4a8fc6282f021ca.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:19.634ex; height:3.009ex;" alt="{\displaystyle k\times 2^{n/2+1}+2^{n-k+1}}" loading="lazy"></span>. The complexity is above <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 2^{n/2}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<msup>
<mn>2</mn>
<mrow class="MJX-TeXAtom-ORD">
<mi>n</mi>
<mrow class="MJX-TeXAtom-ORD">
<mo>/</mo>
</mrow>
<mn>2</mn>
</mrow>
</msup>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle 2^{n/2}}</annotation>
</semantics>
</math></span><img src="./fd18d146490780241da66ffee2950a5f13cf6469.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:4.025ex; height:2.843ex;" alt="{\displaystyle 2^{n/2}}" loading="lazy"></span> but below <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 2^{n}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<msup>
<mn>2</mn>
<mrow class="MJX-TeXAtom-ORD">
<mi>n</mi>
</mrow>
</msup>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle 2^{n}}</annotation>
</semantics>
</math></span><img src="./8226f30650ee4fe4e640c6d2798127e80e9c160d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.381ex; height:2.343ex;" alt="{\displaystyle 2^{n}}" loading="lazy"></span> when messages are long, and that when messages get shorter the complexity of the attack approaches <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 2^{n}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<msup>
<mn>2</mn>
<mrow class="MJX-TeXAtom-ORD">
<mi>n</mi>
</mrow>
</msup>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle 2^{n}}</annotation>
</semantics>
</math></span><img src="./8226f30650ee4fe4e640c6d2798127e80e9c160d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.381ex; height:2.343ex;" alt="{\displaystyle 2^{n}}" loading="lazy"></span>.
</p>
<div class="mw-heading mw-heading2"><h2 id="Miyaguchi–Preneel">Miyaguchi–Preneel</h2></div>
<p>The Miyaguchi–Preneel single-block-length one-way compression function is an extended variant of Matyas–Meyer–Oseas. It was independently proposed by Shoji Miyaguchi and <a href="Bart_Preneel" title="Bart Preneel">Bart Preneel</a>.
</p><p>It feeds each block of the message (<span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle m_{i}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<msub>
<mi>m</mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>i</mi>
</mrow>
</msub>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle m_{i}}</annotation>
</semantics>
</math></span><img src="./95ec8e804f69706d3f5ad235f4f983220c8df7c2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.84ex; height:2.009ex;" alt="{\displaystyle m_{i}}" loading="lazy"></span>) as the plaintext to be encrypted. The output ciphertext is then XORed (⊕) with the same message block (<span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle m_{i}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<msub>
<mi>m</mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>i</mi>
</mrow>
</msub>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle m_{i}}</annotation>
</semantics>
</math></span><img src="./95ec8e804f69706d3f5ad235f4f983220c8df7c2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.84ex; height:2.009ex;" alt="{\displaystyle m_{i}}" loading="lazy"></span>) and then also XORed with the previous hash value (<span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle H_{i-1}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<msub>
<mi>H</mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>i</mi>
<mo>−<!-- − --></mo>
<mn>1</mn>
</mrow>
</msub>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle H_{i-1}}</annotation>
</semantics>
</math></span><img src="./82bfb2b5eaa0f531b23e9f17f7e0ed31c89a8e76.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:4.831ex; height:2.509ex;" alt="{\displaystyle H_{i-1}}" loading="lazy"></span>) to produce the next hash value (<span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle H_{i}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<msub>
<mi>H</mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>i</mi>
</mrow>
</msub>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle H_{i}}</annotation>
</semantics>
</math></span><img src="./7bd0312f590cc5a400008938f3cc304d42ad3986.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.731ex; height:2.509ex;" alt="{\displaystyle H_{i}}" loading="lazy"></span>). The previous hash value (<span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle H_{i-1}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<msub>
<mi>H</mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>i</mi>
<mo>−<!-- − --></mo>
<mn>1</mn>
</mrow>
</msub>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle H_{i-1}}</annotation>
</semantics>
</math></span><img src="./82bfb2b5eaa0f531b23e9f17f7e0ed31c89a8e76.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:4.831ex; height:2.509ex;" alt="{\displaystyle H_{i-1}}" loading="lazy"></span>) is fed as the key to the block cipher. In the first round when there is no previous hash value it uses a constant pre-specified initial value (<span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle H_{0}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<msub>
<mi>H</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>0</mn>
</mrow>
</msub>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle H_{0}}</annotation>
</semantics>
</math></span><img src="./43910602a221b7a4c373791f94793e3008622070.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.985ex; height:2.509ex;" alt="{\displaystyle H_{0}}" loading="lazy"></span>).
</p><p>If the block cipher has different block and key sizes the hash value (<span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle H_{i-1}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<msub>
<mi>H</mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>i</mi>
<mo>−<!-- − --></mo>
<mn>1</mn>
</mrow>
</msub>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle H_{i-1}}</annotation>
</semantics>
</math></span><img src="./82bfb2b5eaa0f531b23e9f17f7e0ed31c89a8e76.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:4.831ex; height:2.509ex;" alt="{\displaystyle H_{i-1}}" loading="lazy"></span>) will have the wrong size for use as the key. The cipher might also have other special requirements on the key. Then the hash value is first fed through the function <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle g}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>g</mi>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle g}</annotation>
</semantics>
</math></span><img src="./d3556280e66fe2c0d0140df20935a6f057381d77.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.116ex; height:2.009ex;" alt="{\displaystyle g}" loading="lazy"></span> to be converted/padded to fit as key for the cipher.
</p><p>In mathematical notation Miyaguchi–Preneel can be described as:
</p>
<dl><dd><span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle H_{i}=E_{g(H_{i-1})}(m_{i})\oplus H_{i-1}\oplus m_{i}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<msub>
<mi>H</mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>i</mi>
</mrow>
</msub>
<mo>=</mo>
<msub>
<mi>E</mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>g</mi>
<mo stretchy="false">(</mo>
<msub>
<mi>H</mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>i</mi>
<mo>−<!-- − --></mo>
<mn>1</mn>
</mrow>
</msub>
<mo stretchy="false">)</mo>
</mrow>
</msub>
<mo stretchy="false">(</mo>
<msub>
<mi>m</mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>i</mi>
</mrow>
</msub>
<mo stretchy="false">)</mo>
<mo>⊕<!-- ⊕ --></mo>
<msub>
<mi>H</mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>i</mi>
<mo>−<!-- − --></mo>
<mn>1</mn>
</mrow>
</msub>
<mo>⊕<!-- ⊕ --></mo>
<msub>
<mi>m</mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>i</mi>
</mrow>
</msub>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle H_{i}=E_{g(H_{i-1})}(m_{i})\oplus H_{i-1}\oplus m_{i}}</annotation>
</semantics>
</math></span><img src="./a9081c9b448d63182516062d23972538cb770397.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.171ex; width:31.543ex; height:3.176ex;" alt="{\displaystyle H_{i}=E_{g(H_{i-1})}(m_{i})\oplus H_{i-1}\oplus m_{i}}" loading="lazy"></span></dd></dl>
<p>The scheme has the rate:
</p>
<dl><dd><span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle R_{MP}={\frac {n}{1\cdot n}}=1}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<msub>
<mi>R</mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>M</mi>
<mi>P</mi>
</mrow>
</msub>
<mo>=</mo>
<mrow class="MJX-TeXAtom-ORD">
<mfrac>
<mi>n</mi>
<mrow>
<mn>1</mn>
<mo>⋅<!-- ⋅ --></mo>
<mi>n</mi>
</mrow>
</mfrac>
</mrow>
<mo>=</mo>
<mn>1</mn>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle R_{MP}={\frac {n}{1\cdot n}}=1}</annotation>
</semantics>
</math></span><img src="./9a5e02951542a8ffc413c559633f074ffa170a7b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.838ex; width:17.389ex; height:4.676ex;" alt="{\displaystyle R_{MP}={\frac {n}{1\cdot n}}=1}" loading="lazy"></span></dd></dl>
<p>The roles of <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle m_{i}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<msub>
<mi>m</mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>i</mi>
</mrow>
</msub>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle m_{i}}</annotation>
</semantics>
</math></span><img src="./95ec8e804f69706d3f5ad235f4f983220c8df7c2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.84ex; height:2.009ex;" alt="{\displaystyle m_{i}}" loading="lazy"></span> and <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle H_{i-1}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<msub>
<mi>H</mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>i</mi>
<mo>−<!-- − --></mo>
<mn>1</mn>
</mrow>
</msub>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle H_{i-1}}</annotation>
</semantics>
</math></span><img src="./82bfb2b5eaa0f531b23e9f17f7e0ed31c89a8e76.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:4.831ex; height:2.509ex;" alt="{\displaystyle H_{i-1}}" loading="lazy"></span> may be switched, so that <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle H_{i-1}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<msub>
<mi>H</mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>i</mi>
<mo>−<!-- − --></mo>
<mn>1</mn>
</mrow>
</msub>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle H_{i-1}}</annotation>
</semantics>
</math></span><img src="./82bfb2b5eaa0f531b23e9f17f7e0ed31c89a8e76.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:4.831ex; height:2.509ex;" alt="{\displaystyle H_{i-1}}" loading="lazy"></span> is encrypted under the key <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle m_{i}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<msub>
<mi>m</mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>i</mi>
</mrow>
</msub>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle m_{i}}</annotation>
</semantics>
</math></span><img src="./95ec8e804f69706d3f5ad235f4f983220c8df7c2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.84ex; height:2.009ex;" alt="{\displaystyle m_{i}}" loading="lazy"></span>, thus making this method an extension of Davies–Meyer instead.
</p>
<div style="clear:both;" class=""></div>
<p>A second preimage attack (given a message <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle m_{1}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<msub>
<mi>m</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>1</mn>
</mrow>
</msub>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle m_{1}}</annotation>
</semantics>
</math></span><img src="./31aafa60e48d39ccce922404c0b80340b2cc777a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:3.095ex; height:2.009ex;" alt="{\displaystyle m_{1}}" loading="lazy"></span> an attacker finds another message <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle m_{2}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<msub>
<mi>m</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>2</mn>
</mrow>
</msub>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle m_{2}}</annotation>
</semantics>
</math></span><img src="./0ecebe334d5cadc3ffcf245eb02919034d7a2ec8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:3.095ex; height:2.009ex;" alt="{\displaystyle m_{2}}" loading="lazy"></span> to satisfy <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \operatorname {hash} (m_{1})=\operatorname {hash} (m_{2})}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>hash</mi>
<mo><!-- --></mo>
<mo stretchy="false">(</mo>
<msub>
<mi>m</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>1</mn>
</mrow>
</msub>
<mo stretchy="false">)</mo>
<mo>=</mo>
<mi>hash</mi>
<mo><!-- --></mo>
<mo stretchy="false">(</mo>
<msub>
<mi>m</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>2</mn>
</mrow>
</msub>
<mo stretchy="false">)</mo>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle \operatorname {hash} (m_{1})=\operatorname {hash} (m_{2})}</annotation>
</semantics>
</math></span><img src="./20df0ccce6e1b89024998c9376a44cbb33d4cc38.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:22.234ex; height:2.843ex;" alt="{\displaystyle \operatorname {hash} (m_{1})=\operatorname {hash} (m_{2})}" loading="lazy"></span>) can be done according to Kelsey and Schneier<sup id="cite_ref-ks05_5-3" class="reference"><a href="#cite_note-ks05-5"><span class="cite-bracket">[</span>5<span class="cite-bracket">]</span></a></sup> for a <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 2^{k}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<msup>
<mn>2</mn>
<mrow class="MJX-TeXAtom-ORD">
<mi>k</mi>
</mrow>
</msup>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle 2^{k}}</annotation>
</semantics>
</math></span><img src="./2d82641ae2702b0db07dd11830af27b9ee0cd196.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.251ex; height:2.676ex;" alt="{\displaystyle 2^{k}}" loading="lazy"></span>-message-block message in time <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k\times 2^{n/2+1}+2^{n-k+1}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>k</mi>
<mo>×<!-- × --></mo>
<msup>
<mn>2</mn>
<mrow class="MJX-TeXAtom-ORD">
<mi>n</mi>
<mrow class="MJX-TeXAtom-ORD">
<mo>/</mo>
</mrow>
<mn>2</mn>
<mo>+</mo>
<mn>1</mn>
</mrow>
</msup>
<mo>+</mo>
<msup>
<mn>2</mn>
<mrow class="MJX-TeXAtom-ORD">
<mi>n</mi>
<mo>−<!-- − --></mo>
<mi>k</mi>
<mo>+</mo>
<mn>1</mn>
</mrow>
</msup>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle k\times 2^{n/2+1}+2^{n-k+1}}</annotation>
</semantics>
</math></span><img src="./b023b5f0466256520b0f97f4c4a8fc6282f021ca.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:19.634ex; height:3.009ex;" alt="{\displaystyle k\times 2^{n/2+1}+2^{n-k+1}}" loading="lazy"></span>. The complexity is above <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 2^{n/2}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<msup>
<mn>2</mn>
<mrow class="MJX-TeXAtom-ORD">
<mi>n</mi>
<mrow class="MJX-TeXAtom-ORD">
<mo>/</mo>
</mrow>
<mn>2</mn>
</mrow>
</msup>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle 2^{n/2}}</annotation>
</semantics>
</math></span><img src="./fd18d146490780241da66ffee2950a5f13cf6469.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:4.025ex; height:2.843ex;" alt="{\displaystyle 2^{n/2}}" loading="lazy"></span> but below <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 2^{n}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<msup>
<mn>2</mn>
<mrow class="MJX-TeXAtom-ORD">
<mi>n</mi>
</mrow>
</msup>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle 2^{n}}</annotation>
</semantics>
</math></span><img src="./8226f30650ee4fe4e640c6d2798127e80e9c160d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.381ex; height:2.343ex;" alt="{\displaystyle 2^{n}}" loading="lazy"></span> when messages are long, and that when messages get shorter the complexity of the attack approaches <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 2^{n}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<msup>
<mn>2</mn>
<mrow class="MJX-TeXAtom-ORD">
<mi>n</mi>
</mrow>
</msup>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle 2^{n}}</annotation>
</semantics>
</math></span><img src="./8226f30650ee4fe4e640c6d2798127e80e9c160d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.381ex; height:2.343ex;" alt="{\displaystyle 2^{n}}" loading="lazy"></span>.
</p>
<div class="mw-heading mw-heading2"><h2 id="Hirose">Hirose</h2></div>
<p>The Hirose<sup id="cite_ref-Hirose06_8-1" class="reference"><a href="#cite_note-Hirose06-8"><span class="cite-bracket">[</span>8<span class="cite-bracket">]</span></a></sup> double-block-length one-way compression function consists of a block cipher plus a permutation <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>p</mi>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle p}</annotation>
</semantics>
</math></span><img src="./81eac1e205430d1f40810df36a0edffdc367af36.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.089ex; width:1.259ex; height:2.009ex;" alt="{\displaystyle p}" loading="lazy"></span>. It was proposed by Shoichi Hirose in 2006 and is based on a work<sup id="cite_ref-11" class="reference"><a href="#cite_note-11"><span class="cite-bracket">[</span>11<span class="cite-bracket">]</span></a></sup> by Mridul Nandi.
</p><p>It uses a block cipher whose key length <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>k</mi>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle k}</annotation>
</semantics>
</math></span><img src="./c3c9a2c7b599b37105512c5d570edc034056dd40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}" loading="lazy"></span> is larger than the block length <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>n</mi>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle n}</annotation>
</semantics>
</math></span><img src="./a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"></span>, and produces a hash of size <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 2n}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mn>2</mn>
<mi>n</mi>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle 2n}</annotation>
</semantics>
</math></span><img src="./134afa8ff09fdddd24b06f289e92e3a045092bd1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.557ex; height:2.176ex;" alt="{\displaystyle 2n}" loading="lazy"></span>. For example, any of the <a href="Advanced_Encryption_Standard_process" title="Advanced Encryption Standard process">AES candidates</a> with a 192- or 256-bit key (and 128-bit block).
</p><p>Each round accepts a portion of the message <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle m_{i}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<msub>
<mi>m</mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>i</mi>
</mrow>
</msub>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle m_{i}}</annotation>
</semantics>
</math></span><img src="./95ec8e804f69706d3f5ad235f4f983220c8df7c2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.84ex; height:2.009ex;" alt="{\displaystyle m_{i}}" loading="lazy"></span> that is <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k-n}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>k</mi>
<mo>−<!-- − --></mo>
<mi>n</mi>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle k-n}</annotation>
</semantics>
</math></span><img src="./863791b18f44ebc09771fb5c0728df2b319c976c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:5.446ex; height:2.343ex;" alt="{\displaystyle k-n}" loading="lazy"></span> bits long, and uses it to update two <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>n</mi>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle n}</annotation>
</semantics>
</math></span><img src="./a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"></span>-bit state values <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>G</mi>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle G}</annotation>
</semantics>
</math></span><img src="./f5f3c8921a3b352de45446a6789b104458c9f90b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.827ex; height:2.176ex;" alt="{\displaystyle G}" loading="lazy"></span> and <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle H}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>H</mi>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle H}</annotation>
</semantics>
</math></span><img src="./75a9edddcca2f782014371f75dca39d7e13a9c1b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.064ex; height:2.176ex;" alt="{\displaystyle H}" loading="lazy"></span>.
</p><p>First, <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle m_{i}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<msub>
<mi>m</mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>i</mi>
</mrow>
</msub>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle m_{i}}</annotation>
</semantics>
</math></span><img src="./95ec8e804f69706d3f5ad235f4f983220c8df7c2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.84ex; height:2.009ex;" alt="{\displaystyle m_{i}}" loading="lazy"></span> is concatenated with <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle H_{i-1}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<msub>
<mi>H</mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>i</mi>
<mo>−<!-- − --></mo>
<mn>1</mn>
</mrow>
</msub>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle H_{i-1}}</annotation>
</semantics>
</math></span><img src="./82bfb2b5eaa0f531b23e9f17f7e0ed31c89a8e76.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:4.831ex; height:2.509ex;" alt="{\displaystyle H_{i-1}}" loading="lazy"></span> to produce a key <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle K_{i}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<msub>
<mi>K</mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>i</mi>
</mrow>
</msub>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle K_{i}}</annotation>
</semantics>
</math></span><img src="./719736a1feb0bd7e73bb1425641a61229f55bb6d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.773ex; height:2.509ex;" alt="{\displaystyle K_{i}}" loading="lazy"></span>. Then the two feedback values are updated according to:
</p>
<ul><li><span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G_{i}=E_{K_{i}}(G_{i-1})\oplus G_{i-1}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<msub>
<mi>G</mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>i</mi>
</mrow>
</msub>
<mo>=</mo>
<msub>
<mi>E</mi>
<mrow class="MJX-TeXAtom-ORD">
<msub>
<mi>K</mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>i</mi>
</mrow>
</msub>
</mrow>
</msub>
<mo stretchy="false">(</mo>
<msub>
<mi>G</mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>i</mi>
<mo>−<!-- − --></mo>
<mn>1</mn>
</mrow>
</msub>
<mo stretchy="false">)</mo>
<mo>⊕<!-- ⊕ --></mo>
<msub>
<mi>G</mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>i</mi>
<mo>−<!-- − --></mo>
<mn>1</mn>
</mrow>
</msub>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle G_{i}=E_{K_{i}}(G_{i-1})\oplus G_{i-1}}</annotation>
</semantics>
</math></span><img src="./1c6b14dbcd76ddecb131eab27fb0cc5fa7670db9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:23.796ex; height:3.009ex;" alt="{\displaystyle G_{i}=E_{K_{i}}(G_{i-1})\oplus G_{i-1}}" loading="lazy"></span></li>
<li><span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle H_{i}=E_{K_{i}}(p(G_{i-1}))\oplus p(G_{i-1})}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<msub>
<mi>H</mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>i</mi>
</mrow>
</msub>
<mo>=</mo>
<msub>
<mi>E</mi>
<mrow class="MJX-TeXAtom-ORD">
<msub>
<mi>K</mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>i</mi>
</mrow>
</msub>
</mrow>
</msub>
<mo stretchy="false">(</mo>
<mi>p</mi>
<mo stretchy="false">(</mo>
<msub>
<mi>G</mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>i</mi>
<mo>−<!-- − --></mo>
<mn>1</mn>
</mrow>
</msub>
<mo stretchy="false">)</mo>
<mo stretchy="false">)</mo>
<mo>⊕<!-- ⊕ --></mo>
<mi>p</mi>
<mo stretchy="false">(</mo>
<msub>
<mi>G</mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>i</mi>
<mo>−<!-- − --></mo>
<mn>1</mn>
</mrow>
</msub>
<mo stretchy="false">)</mo>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle H_{i}=E_{K_{i}}(p(G_{i-1}))\oplus p(G_{i-1})}</annotation>
</semantics>
</math></span><img src="./ffdeabfc9875120edbbea846afa3f72429018aba.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:29.858ex; height:3.009ex;" alt="{\displaystyle H_{i}=E_{K_{i}}(p(G_{i-1}))\oplus p(G_{i-1})}" loading="lazy"></span></li></ul>
<p><span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p(G_{i-1})}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>p</mi>
<mo stretchy="false">(</mo>
<msub>
<mi>G</mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>i</mi>
<mo>−<!-- − --></mo>
<mn>1</mn>
</mrow>
</msub>
<mo stretchy="false">)</mo>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle p(G_{i-1})}</annotation>
</semantics>
</math></span><img src="./c60415780208ce03f6192e3f5284c7c7114bf127.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; margin-left: -0.089ex; width:7.795ex; height:2.843ex;" alt="{\displaystyle p(G_{i-1})}" loading="lazy"></span> is an arbitrary fixed-point-free permutation on an <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>n</mi>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle n}</annotation>
</semantics>
</math></span><img src="./a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"></span>-bit value, typically defined as <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p(x)=x\oplus c}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>p</mi>
<mo stretchy="false">(</mo>
<mi>x</mi>
<mo stretchy="false">)</mo>
<mo>=</mo>
<mi>x</mi>
<mo>⊕<!-- ⊕ --></mo>
<mi>c</mi>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle p(x)=x\oplus c}</annotation>
</semantics>
</math></span><img src="./676609462d63dc692a4587fb7892e33822cb34af.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; margin-left: -0.089ex; width:12.673ex; height:2.843ex;" alt="{\displaystyle p(x)=x\oplus c}" loading="lazy"></span> for an arbitrary non-zero constant <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle c}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>c</mi>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle c}</annotation>
</semantics>
</math></span><img src="./86a67b81c2de995bd608d5b2df50cd8cd7d92455.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.007ex; height:1.676ex;" alt="{\displaystyle c}" loading="lazy"></span> (all ones may be a convenient choice).
</p><p>Each encryption resembles the standard Davies–Meyer construction. The advantage of this scheme over other proposed double-block-length schemes is that both encryptions use the same key, and thus key scheduling effort may be shared.
</p><p>The final output is <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle H_{t}||G_{t}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<msub>
<mi>H</mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>t</mi>
</mrow>
</msub>
<mrow class="MJX-TeXAtom-ORD">
<mo stretchy="false">|</mo>
</mrow>
<mrow class="MJX-TeXAtom-ORD">
<mo stretchy="false">|</mo>
</mrow>
<msub>
<mi>G</mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>t</mi>
</mrow>
</msub>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle H_{t}||G_{t}}</annotation>
</semantics>
</math></span><img src="./19c24696df5e55a1a2c1dc16c8f956a0f380f265.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.704ex; height:2.843ex;" alt="{\displaystyle H_{t}||G_{t}}" loading="lazy"></span>. The scheme has the rate <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\textstyle R_{Hirose}={\frac {k-n}{2n}}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="false" scriptlevel="0">
<msub>
<mi>R</mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>H</mi>
<mi>i</mi>
<mi>r</mi>
<mi>o</mi>
<mi>s</mi>
<mi>e</mi>
</mrow>
</msub>
<mo>=</mo>
<mrow class="MJX-TeXAtom-ORD">
<mfrac>
<mrow>
<mi>k</mi>
<mo>−<!-- − --></mo>
<mi>n</mi>
</mrow>
<mrow>
<mn>2</mn>
<mi>n</mi>
</mrow>
</mfrac>
</mrow>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\textstyle R_{Hirose}={\frac {k-n}{2n}}}</annotation>
</semantics>
</math></span><img src="./85b0710674729b45aaa32ea17ac3a7d2635f1165.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.171ex; width:14.155ex; height:3.676ex;" alt="{\textstyle R_{Hirose}={\frac {k-n}{2n}}}" loading="lazy"></span> relative to encrypting the message with the cipher.
</p><p>Hirose also provides a proof in the Ideal Cipher Model.
</p>
<div class="mw-heading mw-heading2"><h2 id="Sponge_construction">Sponge construction</h2></div>
<p>The <a href="Sponge_construction" class="mw-redirect" title="Sponge construction">sponge construction</a> can be used to build one-way compression functions.
</p>
<div class="mw-heading mw-heading2"><h2 id="See_also">See also</h2></div>
<ul><li><a href="Whirlpool_(cryptography)" class="mw-redirect" title="Whirlpool (cryptography)">Whirlpool</a> — A cryptographic hash function built using the Miyaguchi–Preneel construction and a block cipher similar to <a href="Square_(cipher)" title="Square (cipher)">Square</a> and <a href="Advanced_Encryption_Standard" title="Advanced Encryption Standard">AES</a>.</li>
<li><a href="CBC-MAC" title="CBC-MAC">CBC-MAC</a>, <a href="One-key_MAC" title="One-key MAC">OMAC</a>, and <a href="PMAC_(cryptography)" title="PMAC (cryptography)">PMAC</a> — Methods to turn block ciphers into <a href="Message_authentication_code" title="Message authentication code">message authentication codes</a> (MACs).</li></ul>
<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>
<div class="mw-heading mw-heading3"><h3 id="Citations">Citations</h3></div>
<style data-mw-deduplicate="TemplateStyles:r1239543626">
/* start https://en.wikipedia.org/ */
.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}
/* end https://en.wikipedia.org/ */
</style><div class="reflist">
<div class="mw-references-wrap mw-references-columns"><ol class="references">
<li id="cite_note-:0-1"><span class="mw-cite-backlink">^ <a href="#cite_ref-:0_1-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-:0_1-1"><sup><i><b>b</b></i></sup></a></span> <span class="reference-text">Handbook of Applied Cryptography by Alfred J. Menezes, Paul C. van Oorschot, Scott A. Vanstone. Fifth Printing (August 2001) page 328.</span>
</li>
<li id="cite_note-2"><span class="mw-cite-backlink"><b><a href="#cite_ref-2">^</a></b></span> <span class="reference-text"><style data-mw-deduplicate="TemplateStyles:r1238218222">
/* start https://en.wikipedia.org/ */
.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}
/* end https://en.wikipedia.org/ */
</style><cite class="citation web cs1"><a rel="nofollow" class="external text" href="https://security.googleblog.com/2017/02/announcing-first-sha1-collision.html">"Announcing the first SHA1 collision"</a>. <i>Google Online Security Blog</i><span class="reference-accessdate">. Retrieved <span class="nowrap">2020-01-12</span></span>.</cite></span>
</li>
<li id="cite_note-damgard89-3"><span class="mw-cite-backlink"><b><a href="#cite_ref-damgard89_3-0">^</a></b></span> <span class="reference-text">Ivan Damgård. <a rel="nofollow" class="external text" href="https://link.springer.com/content/pdf/10.1007%2F0-387-34805-0_39.pdf">A design principle for hash functions</a>. In Gilles Brassard, editor, CRYPTO, volume 435 of LNCS, pages 416–427. Springer, 1989.</span>
</li>
<li id="cite_note-merkle89-4"><span class="mw-cite-backlink"><b><a href="#cite_ref-merkle89_4-0">^</a></b></span> <span class="reference-text">Ralph Merkle. <a rel="nofollow" class="external text" href="https://link.springer.com/content/pdf/10.1007%2F0-387-34805-0_40.pdf">One way hash functions and DES</a>. In Gilles Brassard, editor, CRYPTO, volume 435 of LNCS, pages 428–446. Springer, 1989.</span>
</li>
<li id="cite_note-ks05-5"><span class="mw-cite-backlink">^ <a href="#cite_ref-ks05_5-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-ks05_5-1"><sup><i><b>b</b></i></sup></a> <a href="#cite_ref-ks05_5-2"><sup><i><b>c</b></i></sup></a> <a href="#cite_ref-ks05_5-3"><sup><i><b>d</b></i></sup></a></span> <span class="reference-text">John Kelsey and Bruce Schneier. <a rel="nofollow" class="external text" href="https://www.schneier.com/academic/paperfiles/paper-preimages.pdf">Second preimages on <i>n</i>-bit hash functions for much less than 2<sup><i>n</i></sup> work</a>. In Ronald Cramer, editor, EUROCRYPT, volume 3494 of LNCS, pages 474–490. Springer, 2005.</span>
</li>
<li id="cite_note-6"><span class="mw-cite-backlink"><b><a href="#cite_ref-6">^</a></b></span> <span class="reference-text">John Black, Martin Cochran, and Thomas Shrimpton. <i>On the Impossibility of Highly-Efficient Blockcipher-Based Hash Functions.</i> Advances in Cryptology – EUROCRYPT '05, Aarhus, Denmark, 2005. The authors define a hash function "highly efficient if its compression function uses exactly one call to a block cipher whose key is fixed".</span>
</li>
<li id="cite_note-7"><span class="mw-cite-backlink"><b><a href="#cite_ref-7">^</a></b></span> <span class="reference-text">John Black, Phillip Rogaway, and Tom Shrimpton. <i>Black-Box Analysis of the Block-Cipher-Based Hash-Function Constructions from PGV.</i> Advances in Cryptology – CRYPTO '02, Lecture Notes in Computer Science, vol. 2442, pp. 320–335, Springer, 2002. See the table on page 3, Davies–Meyer, Matyas–Meyer–Oseas and Miyaguchi–Preneel are numbered in the first column as hash functions 5, 1 and 3.</span>
</li>
<li id="cite_note-Hirose06-8"><span class="mw-cite-backlink">^ <a href="#cite_ref-Hirose06_8-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-Hirose06_8-1"><sup><i><b>b</b></i></sup></a></span> <span class="reference-text">S. Hirose, <i><a rel="nofollow" class="external text" href="https://www.iacr.org/archive/fse2006/40470213/40470213.pdf">Some Plausible Constructions of Double-Block-Length Hash Functions</a></i>. In: Robshaw, M. J. B. (ed.) FSE 2006, LNCS, vol. 4047, pp. 210–225, Springer, Heidelberg 2006.</span>
</li>
<li id="cite_note-9"><span class="mw-cite-backlink"><b><a href="#cite_ref-9">^</a></b></span> <span class="reference-text">Handbook of Applied Cryptography by Alfred J. Menezes, Paul C. van Oorschot, Scott A. Vanstone. Fifth Printing (August 2001) page 375.</span>
</li>
<li id="cite_note-10"><span class="mw-cite-backlink"><b><a href="#cite_ref-10">^</a></b></span> <span class="reference-text">R. Winternitz. <i>A secure one-way hash function built from DES.</i> In Proceedings of the IEEE Symposium on Information Security and Privacy, p. 88-90. IEEE Press, 1984.</span>
</li>
<li id="cite_note-11"><span class="mw-cite-backlink"><b><a href="#cite_ref-11">^</a></b></span> <span class="reference-text">M. Nandi, <i>Towards optimal double-length hash functions</i>, In: Proceedings of the 6th International Conference on Cryptology in India (INDOCRYPT 2005), Lecture Notes in Computer Science 3797, pages 77–89, 2005.</span>
</li>
</ol></div></div>
<div class="mw-heading mw-heading3"><h3 id="Sources">Sources</h3></div>
<style data-mw-deduplicate="TemplateStyles:r1239549316">
/* start https://en.wikipedia.org/ */
.mw-parser-output .refbegin{margin-bottom:0.5em}.mw-parser-output .refbegin-hanging-indents>ul{margin-left:0}.mw-parser-output .refbegin-hanging-indents>ul>li{margin-left:0;padding-left:3.2em;text-indent:-3.2em}.mw-parser-output .refbegin-hanging-indents ul,.mw-parser-output .refbegin-hanging-indents ul li{list-style:none}@media(max-width:720px){.mw-parser-output .refbegin-hanging-indents>ul>li{padding-left:1.6em;text-indent:-1.6em}}.mw-parser-output .refbegin-columns{margin-top:0.3em}.mw-parser-output .refbegin-columns ul{margin-top:0}.mw-parser-output .refbegin-columns li{page-break-inside:avoid;break-inside:avoid-column}@media screen{.mw-parser-output .refbegin{font-size:90%}}
/* end https://en.wikipedia.org/ */
</style><div class="refbegin" style="">
<ul><li><cite id="CITEREFMenezesvan_OorschotVanstone2001" class="citation book cs1">Menezes; van Oorschot; Vanstone (2001). <a rel="nofollow" class="external text" href="http://cacr.uwaterloo.ca/hac/about/chap9.pdf">"Hash Functions and Data Integrity"</a> <span class="cs1-format">(PDF)</span>. <a rel="nofollow" class="external text" href="http://cacr.uwaterloo.ca/hac/"><i>Handbook of Applied Cryptography</i></a>.</cite></li></ul>
</div>
<div class="navbox-styles"><style data-mw-deduplicate="TemplateStyles:r1129693374">
/* start https://en.wikipedia.org/ */
.mw-parser-output .hlist dl,.mw-parser-output .hlist ol,.mw-parser-output .hlist ul{margin:0;padding:0}.mw-parser-output .hlist dd,.mw-parser-output .hlist dt,.mw-parser-output .hlist li{margin:0;display:inline}.mw-parser-output .hlist.inline,.mw-parser-output .hlist.inline dl,.mw-parser-output .hlist.inline ol,.mw-parser-output .hlist.inline ul,.mw-parser-output .hlist dl dl,.mw-parser-output .hlist dl ol,.mw-parser-output .hlist dl ul,.mw-parser-output .hlist ol dl,.mw-parser-output .hlist ol ol,.mw-parser-output .hlist ol ul,.mw-parser-output .hlist ul dl,.mw-parser-output .hlist ul ol,.mw-parser-output .hlist ul ul{display:inline}.mw-parser-output .hlist .mw-empty-li{display:none}.mw-parser-output .hlist dt::after{content:": "}.mw-parser-output .hlist dd::after,.mw-parser-output .hlist li::after{content:" · ";font-weight:bold}.mw-parser-output .hlist dd:last-child::after,.mw-parser-output .hlist dt:last-child::after,.mw-parser-output .hlist li:last-child::after{content:none}.mw-parser-output .hlist dd dd:first-child::before,.mw-parser-output .hlist dd dt:first-child::before,.mw-parser-output .hlist dd li:first-child::before,.mw-parser-output .hlist dt dd:first-child::before,.mw-parser-output .hlist dt dt:first-child::before,.mw-parser-output .hlist dt li:first-child::before,.mw-parser-output .hlist li dd:first-child::before,.mw-parser-output .hlist li dt:first-child::before,.mw-parser-output .hlist li li:first-child::before{content:" (";font-weight:normal}.mw-parser-output .hlist dd dd:last-child::after,.mw-parser-output .hlist dd dt:last-child::after,.mw-parser-output .hlist dd li:last-child::after,.mw-parser-output .hlist dt dd:last-child::after,.mw-parser-output .hlist dt dt:last-child::after,.mw-parser-output .hlist dt li:last-child::after,.mw-parser-output .hlist li dd:last-child::after,.mw-parser-output .hlist li dt:last-child::after,.mw-parser-output .hlist li li:last-child::after{content:")";font-weight:normal}.mw-parser-output .hlist ol{counter-reset:listitem}.mw-parser-output .hlist ol>li{counter-increment:listitem}.mw-parser-output .hlist ol>li::before{content:" "counter(listitem)"\a0 "}.mw-parser-output .hlist dd ol>li:first-child::before,.mw-parser-output .hlist dt ol>li:first-child::before,.mw-parser-output .hlist li ol>li:first-child::before{content:" ("counter(listitem)"\a0 "}
/* end https://en.wikipedia.org/ */
</style><style data-mw-deduplicate="TemplateStyles:r1236075235">
/* start https://en.wikipedia.org/ */
.mw-parser-output .navbox{box-sizing:border-box;border:1px solid #a2a9b1;width:100%;clear:both;font-size:88%;text-align:center;padding:1px;margin:1em auto 0}.mw-parser-output .navbox .navbox{margin-top:0}.mw-parser-output .navbox+.navbox,.mw-parser-output .navbox+.navbox-styles+.navbox{margin-top:-1px}.mw-parser-output .navbox-inner,.mw-parser-output .navbox-subgroup{width:100%}.mw-parser-output .navbox-group,.mw-parser-output .navbox-title,.mw-parser-output .navbox-abovebelow{padding:0.25em 1em;line-height:1.5em;text-align:center}.mw-parser-output .navbox-group{white-space:nowrap;text-align:right}.mw-parser-output .navbox,.mw-parser-output .navbox-subgroup{background-color:#fdfdfd}.mw-parser-output .navbox-list{line-height:1.5em;border-color:#fdfdfd}.mw-parser-output .navbox-list-with-group{text-align:left;border-left-width:2px;border-left-style:solid}.mw-parser-output tr+tr>.navbox-abovebelow,.mw-parser-output tr+tr>.navbox-group,.mw-parser-output tr+tr>.navbox-image,.mw-parser-output tr+tr>.navbox-list{border-top:2px solid #fdfdfd}.mw-parser-output .navbox-title{background-color:#ccf}.mw-parser-output .navbox-abovebelow,.mw-parser-output .navbox-group,.mw-parser-output .navbox-subgroup .navbox-title{background-color:#ddf}.mw-parser-output .navbox-subgroup .navbox-group,.mw-parser-output .navbox-subgroup .navbox-abovebelow{background-color:#e6e6ff}.mw-parser-output .navbox-even{background-color:#f7f7f7}.mw-parser-output .navbox-odd{background-color:transparent}.mw-parser-output .navbox .hlist td dl,.mw-parser-output .navbox .hlist td ol,.mw-parser-output .navbox .hlist td ul,.mw-parser-output .navbox td.hlist dl,.mw-parser-output .navbox td.hlist ol,.mw-parser-output .navbox td.hlist ul{padding:0.125em 0}.mw-parser-output .navbox .navbar{display:block;font-size:100%}.mw-parser-output .navbox-title .navbar{float:left;text-align:left;margin-right:0.5em}body.skin--responsive .mw-parser-output .navbox-image img{max-width:none!important}@media print{body.ns-0 .mw-parser-output .navbox{display:none!important}}
/* end https://en.wikipedia.org/ */
</style><style data-mw-deduplicate="TemplateStyles:r1239400231">
/* start https://en.wikipedia.org/ */
.mw-parser-output .navbar{display:inline;font-size:88%;font-weight:normal}.mw-parser-output .navbar-collapse{float:left;text-align:left}.mw-parser-output .navbar-boxtext{word-spacing:0}.mw-parser-output .navbar ul{display:inline-block;white-space:nowrap;line-height:inherit}.mw-parser-output .navbar-brackets::before{margin-right:-0.125em;content:"[ "}.mw-parser-output .navbar-brackets::after{margin-left:-0.125em;content:" ]"}.mw-parser-output .navbar li{word-spacing:-0.125em}.mw-parser-output .navbar a>span,.mw-parser-output .navbar a>abbr{text-decoration:inherit}.mw-parser-output .navbar-mini abbr{font-variant:small-caps;border-bottom:none;text-decoration:none;cursor:inherit}.mw-parser-output .navbar-ct-full{font-size:114%;margin:0 7em}.mw-parser-output .navbar-ct-mini{font-size:114%;margin:0 4em}html.skin-theme-clientpref-night .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}@media(prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}}@media print{.mw-parser-output .navbar{display:none!important}}
/* end https://en.wikipedia.org/ */
</style></div><div role="navigation" class="navbox" aria-label="Navbox0" style="padding:3px"><table class="nowraplinks hlist navbox-inner" style="border-spacing:0;background:transparent;color:inherit"><tbody><tr><td colspan="2" class="navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"></div><table class="nowraplinks navbox-subgroup" style="border-spacing:0"><tbody><tr><td colspan="2" class="navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"></div><table class="nowraplinks hlist mw-collapsible mw-collapsed navbox-subgroup" style="border-spacing:0"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><div id="Cryptographic_hash_functions_and_message_authentication_codes539" style="font-size:114%;margin:0 4em"><a href="Cryptographic_hash_function" title="Cryptographic hash function">Cryptographic hash functions</a> and <a href="Message_authentication_code" title="Message authentication code">message authentication codes</a></div></th></tr><tr><td class="navbox-abovebelow" colspan="2"><div>
<ul><li><a href="List_of_hash_functions" title="List of hash functions">List</a></li>
<li><a href="Comparison_of_cryptographic_hash_functions" title="Comparison of cryptographic hash functions">Comparison</a></li>
<li><a href="Hash_function_security_summary" title="Hash function security summary">Known attacks</a></li></ul>
</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Common functions</th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">
<ul><li><a href="MD5" title="MD5">MD5</a> (compromised)</li>
<li><a href="SHA-1" title="SHA-1">SHA-1</a> (compromised)</li>
<li><a href="SHA-2" title="SHA-2">SHA-2</a></li>
<li><a href="SHA-3" title="SHA-3">SHA-3</a></li>
<li><a href="BLAKE_(hash_function)#BLAKE2" title="BLAKE (hash function)">BLAKE2</a></li></ul>
</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="NIST_hash_function_competition" title="NIST hash function competition">SHA-3 finalists</a></th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">
<ul><li><a href="BLAKE_(hash_function)" title="BLAKE (hash function)">BLAKE</a></li>
<li><a href="Gr%C3%B8stl" title="Grøstl">Grøstl</a></li>
<li><a href="JH_(hash_function)" title="JH (hash function)">JH</a></li>
<li><a href="Skein_(hash_function)" title="Skein (hash function)">Skein</a></li>
<li><a href="SHA-3" title="SHA-3">Keccak</a> (winner)</li></ul>
</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Other functions</th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">
<ul><li><a href="BLAKE3" class="mw-redirect" title="BLAKE3">BLAKE3</a></li>
<li><a href="CubeHash" title="CubeHash">CubeHash</a></li>
<li><a href="Elliptic_curve_only_hash" title="Elliptic curve only hash">ECOH</a></li>
<li><a href="Fast_syndrome-based_hash" title="Fast syndrome-based hash">FSB</a></li>
<li><a href="Fugue_(hash_function)" title="Fugue (hash function)">Fugue</a></li>
<li><a href="GOST_(hash_function)" title="GOST (hash function)">GOST</a></li>
<li><a href="HAS-160" title="HAS-160">HAS-160</a></li>
<li><a href="HAVAL" title="HAVAL">HAVAL</a></li>
<li><a href="Kupyna" title="Kupyna">Kupyna</a></li>
<li><a href="LSH_(hash_function)" title="LSH (hash function)">LSH</a></li>
<li><a href="Lane_(hash_function)" title="Lane (hash function)">Lane</a></li>
<li><a href="MASH-1" title="MASH-1">MASH-1</a></li>
<li><a href="MASH-1#MASH2" title="MASH-1">MASH-2</a></li>
<li><a href="MD2_(hash_function)" title="MD2 (hash function)">MD2</a></li>
<li><a href="MD4" title="MD4">MD4</a></li>
<li><a href="MD6" title="MD6">MD6</a></li>
<li><a href="MDC-2" title="MDC-2">MDC-2</a></li>
<li><a href="N-hash" title="N-hash">N-hash</a></li>
<li><a href="RIPEMD" title="RIPEMD">RIPEMD</a></li>
<li><a href="RadioGat%C3%BAn" title="RadioGatún">RadioGatún</a></li>
<li><a href="SIMD_(hash_function)" title="SIMD (hash function)">SIMD</a></li>
<li><a href="SM3_(hash_function)" title="SM3 (hash function)">SM3</a></li>
<li><a href="SWIFFT" title="SWIFFT">SWIFFT</a></li>
<li><a href="Shabal" title="Shabal">Shabal</a></li>
<li><a href="Snefru" title="Snefru">Snefru</a></li>
<li><a href="Streebog" title="Streebog">Streebog</a></li>
<li><a href="Tiger_(hash_function)" title="Tiger (hash function)">Tiger</a></li>
<li><a href="Very_smooth_hash" title="Very smooth hash">VSH</a></li>
<li><a href="Whirlpool_(hash_function)" title="Whirlpool (hash function)">Whirlpool</a></li></ul>
</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Password hashing/<br><a href="Key_stretching" title="Key stretching">key stretching</a> functions</th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">
<ul><li><a href="Argon2" title="Argon2">Argon2</a></li>
<li><a href="Balloon_hashing" title="Balloon hashing">Balloon</a></li>
<li><a href="Bcrypt" title="Bcrypt">bcrypt</a></li>
<li><a href="Catena_(cryptography)" class="mw-redirect" title="Catena (cryptography)">Catena</a></li>
<li><a href="Crypt_(C)" title="Crypt (C)">crypt</a></li>
<li><a href="LAN_Manager#LM_hash_details" title="LAN Manager">LM hash</a></li>
<li><a href="Lyra2" title="Lyra2">Lyra2</a></li>
<li><a href="Makwa_(cryptography)" class="mw-redirect" title="Makwa (cryptography)">Makwa</a></li>
<li><a href="PBKDF2" title="PBKDF2">PBKDF2</a></li>
<li><a href="Scrypt" title="Scrypt">scrypt</a></li>
<li><a href="Yescrypt" title="Yescrypt">yescrypt</a></li></ul>
</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">General purpose<br><a href="Key_derivation_function" title="Key derivation function">key derivation functions</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">
<ul><li><a href="HKDF" title="HKDF">HKDF</a></li>
<li>KDF1/KDF2</li></ul>
</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Message_authentication_code" title="Message authentication code">MAC functions</a></th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">
<ul><li><a href="CBC-MAC" title="CBC-MAC">CBC-MAC</a></li>
<li><a href="Data_Authentication_Algorithm" title="Data Authentication Algorithm">DAA</a></li>
<li><a href="Galois_Message_Authentication_Code" class="mw-redirect" title="Galois Message Authentication Code">GMAC</a></li>
<li><a href="HMAC" title="HMAC">HMAC</a></li>
<li><a href="NMAC" class="mw-redirect" title="NMAC">NMAC</a></li>
<li><a href="One-key_MAC" title="One-key MAC">OMAC</a>/<a href="One-key_MAC" title="One-key MAC">CMAC</a></li>
<li><a href="PMAC_(cryptography)" title="PMAC (cryptography)">PMAC</a></li>
<li><a href="Poly1305" title="Poly1305">Poly1305</a></li>
<li><a href="SipHash" title="SipHash">SipHash</a></li>
<li><a href="UMAC_(cryptography)" title="UMAC (cryptography)">UMAC</a></li>
<li><a href="VMAC" title="VMAC">VMAC</a></li></ul>
</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Authenticated_encryption" title="Authenticated encryption">Authenticated<br>encryption</a> modes</th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">
<ul><li><a href="CCM_mode" title="CCM mode">CCM</a></li>
<li><a href="ChaCha20-Poly1305" title="ChaCha20-Poly1305">ChaCha20-Poly1305</a></li>
<li><a href="CWC_mode" title="CWC mode">CWC</a></li>
<li><a href="EAX_mode" title="EAX mode">EAX</a></li>
<li><a href="Galois/Counter_Mode" title="Galois/Counter Mode">GCM</a></li>
<li><a href="IAPM_(mode)" title="IAPM (mode)">IAPM</a></li>
<li><a href="OCB_mode" title="OCB mode">OCB</a></li></ul>
</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Attacks</th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">
<ul><li><a href="Collision_attack" title="Collision attack">Collision attack</a></li>
<li><a href="Preimage_attack" title="Preimage attack">Preimage attack</a></li>
<li><a href="Birthday_attack" title="Birthday attack">Birthday attack</a></li>
<li><a href="Brute-force_attack" title="Brute-force attack">Brute-force attack</a></li>
<li><a href="Rainbow_table" title="Rainbow table">Rainbow table</a></li>
<li><a href="Side-channel_attack" title="Side-channel attack">Side-channel attack</a></li>
<li><a href="Length_extension_attack" title="Length extension attack">Length extension attack</a></li></ul>
</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Design</th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">
<ul><li><a href="Avalanche_effect" title="Avalanche effect">Avalanche effect</a></li>
<li><a href="Hash_collision" title="Hash collision">Hash collision</a></li>
<li><a href="Merkle%E2%80%93Damg%C3%A5rd_construction" title="Merkle–Damgård construction">Merkle–Damgård construction</a></li>
<li><a href="Sponge_function" title="Sponge function">Sponge function</a></li>
<li><a href="HAIFA_construction" title="HAIFA construction">HAIFA construction</a></li></ul>
</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Standardization</th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">
<ul><li><a href="CAESAR_Competition" title="CAESAR Competition">CAESAR Competition</a></li>
<li><a href="CRYPTREC" title="CRYPTREC">CRYPTREC</a></li>
<li><a href="NESSIE" title="NESSIE">NESSIE</a></li>
<li><a href="NIST_hash_function_competition" title="NIST hash function competition">NIST hash function competition</a></li>
<li><a href="Password_Hashing_Competition" title="Password Hashing Competition">Password Hashing Competition</a></li>
<li><a href="NSA_Suite_B_Cryptography" title="NSA Suite B Cryptography">NSA Suite B</a></li>
<li><a href="Commercial_National_Security_Algorithm_Suite" title="Commercial National Security Algorithm Suite">CNSA</a></li></ul>
</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Utilization</th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">
<ul><li><a href="Post-quantum_cryptography#Hash-based_cryptography" title="Post-quantum cryptography">Hash-based cryptography</a></li>
<li><a href="Merkle_tree" title="Merkle tree">Merkle tree</a></li>
<li><a href="Message_authentication" title="Message authentication">Message authentication</a></li>
<li><a href="Proof_of_work" title="Proof of work">Proof of work</a></li>
<li><a href="Salt_(cryptography)" title="Salt (cryptography)">Salt</a></li>
<li><a href="Pepper_(cryptography)" title="Pepper (cryptography)">Pepper</a></li></ul>
</div></td></tr></tbody></table><div></div></td></tr></tbody></table><div></div></td></tr><tr><td colspan="2" class="navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"></div><table class="nowraplinks mw-collapsible mw-collapsed navbox-subgroup" style="border-spacing:0"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><div id="Cryptography149" style="font-size:114%;margin:0 4em"><a href="Cryptography" title="Cryptography">Cryptography</a></div></th></tr><tr><th scope="row" class="navbox-group" style="width:1%">General</th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">
<ul><li><a href="History_of_cryptography" title="History of cryptography">History of cryptography</a></li>
<li><a href="Outline_of_cryptography" title="Outline of cryptography">Outline of cryptography</a></li>
<li><a href="Classical_cipher" title="Classical cipher">Classical cipher</a></li>
<li><a href="Cryptographic_protocol" title="Cryptographic protocol">Cryptographic protocol</a>
<ul><li><a href="Authentication_protocol" title="Authentication protocol">Authentication protocol</a></li></ul></li>
<li><a href="Cryptographic_primitive" title="Cryptographic primitive">Cryptographic primitive</a></li>
<li><a href="Cryptanalysis" title="Cryptanalysis">Cryptanalysis</a></li>
<li><a href="Cryptocurrency" title="Cryptocurrency">Cryptocurrency</a></li>
<li><a href="Cryptosystem" title="Cryptosystem">Cryptosystem</a></li>
<li><a href="Cryptographic_nonce" title="Cryptographic nonce">Cryptographic nonce</a></li>
<li><a href="Cryptovirology" title="Cryptovirology">Cryptovirology</a></li>
<li><a href="Hash_function" title="Hash function">Hash function</a>
<ul><li><a href="Cryptographic_hash_function" title="Cryptographic hash function">Cryptographic hash function</a></li>
<li><a href="Key_derivation_function" title="Key derivation function">Key derivation function</a></li>
<li><a href="Secure_Hash_Algorithms" title="Secure Hash Algorithms">Secure Hash Algorithms</a></li></ul></li>
<li><a href="Digital_signature" title="Digital signature">Digital signature</a></li>
<li><a href="Kleptography" title="Kleptography">Kleptography</a></li>
<li><a href="Key_(cryptography)" title="Key (cryptography)">Key (cryptography)</a></li>
<li><a href="Key_exchange" title="Key exchange">Key exchange</a></li>
<li><a href="Key_generator" title="Key generator">Key generator</a></li>
<li><a href="Key_schedule" title="Key schedule">Key schedule</a></li>
<li><a href="Key_stretching" title="Key stretching">Key stretching</a></li>
<li><a href="Keygen" title="Keygen">Keygen</a></li>
<li>Machines</li>
<li><a href="Cryptojacking_malware" class="mw-redirect" title="Cryptojacking malware">Cryptojacking malware</a></li>
<li><a href="Ransomware" title="Ransomware">Ransomware</a></li>
<li><a href="Random_number_generation" title="Random number generation">Random number generation</a>
<ul><li><a href="Cryptographically_secure_pseudorandom_number_generator" title="Cryptographically secure pseudorandom number generator">Cryptographically secure pseudorandom number generator</a> (CSPRNG)</li></ul></li>
<li><a href="Pseudorandom_noise" title="Pseudorandom noise">Pseudorandom noise</a> (PRN)</li>
<li><a href="Secure_channel" title="Secure channel">Secure channel</a></li>
<li><a href="Insecure_channel" class="mw-redirect" title="Insecure channel">Insecure channel</a></li>
<li><a href="Subliminal_channel" title="Subliminal channel">Subliminal channel</a></li>
<li><a href="Encryption" title="Encryption">Encryption</a></li>
<li><a href="Decryption" class="mw-redirect" title="Decryption">Decryption</a></li>
<li><a href="End-to-end_encryption" title="End-to-end encryption">End-to-end encryption</a></li>
<li><a href="Harvest_now%2C_decrypt_later" title="Harvest now, decrypt later">Harvest now, decrypt later</a></li>
<li><a href="Information-theoretic_security" title="Information-theoretic security">Information-theoretic security</a></li>
<li><a href="Plaintext" title="Plaintext">Plaintext</a></li>
<li><a href="Codetext" class="mw-redirect" title="Codetext">Codetext</a></li>
<li><a href="Ciphertext" title="Ciphertext">Ciphertext</a></li>
<li><a href="Shared_secret" title="Shared secret">Shared secret</a></li>
<li><a href="Trapdoor_function" title="Trapdoor function">Trapdoor function</a></li>
<li><a href="Trusted_timestamping" title="Trusted timestamping">Trusted timestamping</a></li>
<li><a href="Key-based_routing" title="Key-based routing">Key-based routing</a></li>
<li><a href="Onion_routing" title="Onion routing">Onion routing</a></li>
<li><a href="Garlic_routing" title="Garlic routing">Garlic routing</a></li>
<li><a href="Kademlia" title="Kademlia">Kademlia</a></li>
<li><a href="Mix_network" title="Mix network">Mix network</a></li></ul>
</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Mathematics</th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">
<ul><li><a href="Cryptographic_hash_function" title="Cryptographic hash function">Cryptographic hash function</a></li>
<li><a href="Block_cipher" title="Block cipher">Block cipher</a></li>
<li><a href="Stream_cipher" title="Stream cipher">Stream cipher</a></li>
<li><a href="Symmetric-key_algorithm" title="Symmetric-key algorithm">Symmetric-key algorithm</a></li>
<li><a href="Authenticated_encryption" title="Authenticated encryption">Authenticated encryption</a></li>
<li><a href="Public-key_cryptography" title="Public-key cryptography">Public-key cryptography</a></li>
<li><a href="Quantum_key_distribution" title="Quantum key distribution">Quantum key distribution</a></li>
<li><a href="Quantum_cryptography" title="Quantum cryptography">Quantum cryptography</a></li>
<li><a href="Post-quantum_cryptography" title="Post-quantum cryptography">Post-quantum cryptography</a></li>
<li><a href="Message_authentication_code" title="Message authentication code">Message authentication code</a></li>
<li><a href="Cryptographically_secure_pseudorandom_number_generator" title="Cryptographically secure pseudorandom number generator">Random numbers</a></li>
<li><a href="Steganography" title="Steganography">Steganography</a></li></ul>
</div></td></tr><tr><td class="navbox-abovebelow" colspan="2"><div>
<ul><li><span class="noviewer" typeof="mw:File"><span title="Category"></span></span> Category</li></ul>
</div></td></tr></tbody></table><div></div></td></tr></tbody></table></div></div><!--htdig_noindex--><div><div class="zim-footer">
This article is issued from <a class="external text" title="Last edited on 2025-03-24" href="https://en.wikipedia.org/wiki/?title=One-way_compression_function&oldid=1282109930">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.
</div>
</div><!--/htdig_noindex--></div>
</div>
</main>
</div>
</div>
</div>
</body></html>